QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #341787 | #143. 最大流（随机数据） | lhcqwq# | Compile Error | / | / | C++14 | 4.8kb | 2024-02-29 21:22:21 | 2024-02-29 21:22:21 |
Judging History
answer
#include <bits/stdc++.h>
#define rfor(i,l,r) for(int i=l;i<=r;i++)
#define irfor(i,r,l) for(int i=r;i>=l;i--)
#define y0 hfgdsgxdhrarsgtiddfndksgrsgilhfs
#define y1 qwertyuioplkjhgfdsazxcvbnmafdzds
#define ls(p) p<<1
#define rs(p) p<<1|1
#define mkp make_pair
using namespace std;typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair<int,int> pii;
inline ll read(){ll x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;}
inline ll qpow(ll a,ll b,ll p){ll ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
inline void gmin(int &a,int b){if(b<a)a=b;}inline void gmin(ll &a,ll b){if(b<a)a=b;}
inline void gmax(int &a,int b){if(b>a)a=b;}inline void gmax(ll &a,ll b){if(b>a)a=b;}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline ll max(ll a,ll b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
const int N = 205,M = 5005,mod=1e9+7;
int n,m,s,t;
struct edge{int to,nxt;ll dis;edge(int to=0,int nxt=0,ll dis=0):to(to),nxt(nxt),dis(dis){}}e[M*2];int head[N],cnt=1;
void adde(int u,int v,int w){e[++cnt]=edge(v,head[u],w);head[u]=cnt;}
int d[N],now[N];
queue<int> q;
bool bfs()
{
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
q.push(s);d[s]=1;now[s] = head[s];
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = head[u];i;i = e[i].nxt)
{
int v = e[i].to;ll w = e[i].dis;
if(w && !d[v])
{
q.push(v);now[v] = head[v];d[v] = d[u]+1;
if(v == t) return 1;
}
}
}
return 0;
}
ll dinic(int u,ll flow)
{
if(u == t) return flow;
ll rest = flow,i;
for(i = now[u];i;i = e[i].nxt)
{
int v = e[i].to;ll w = e[i].dis;
if(w && d[v] == d[u]+1)
{
ll fl = dinic(v,min(w,rest));
if(!fl) d[v] = 0;
e[i].dis -= fl;e[i^1].dis += fl;
rest -= fl;
}
if(!rest) break;
}
now[u] = i;
return flow - rest;
}
inline void solve()
{
cin >> n >> m >> s >> t;
rfor(i,1,m)
{
int u,v,w;
cin >> u >> v >> w;
adde(u,v,w);
adde(v,u,0);
}
ll flow = 0,ans = 0;
while(bfs())
{
do
{
flow = dinic(s,1e18);
ans += flow;
}while(flow);
}
cout << ans;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;//cin >> t;
while(t--) solve();
return 0;
}#include <bits/stdc++.h>
#define rfor(i,l,r) for(int i=l;i<=r;i++)
#define irfor(i,r,l) for(int i=r;i>=l;i--)
#define y0 hfgdsgxdhrarsgtiddfndksgrsgilhfs
#define y1 qwertyuioplkjhgfdsazxcvbnmafdzds
#define ls(p) p<<1
#define rs(p) p<<1|1
#define mkp make_pair
using namespace std;typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair<int,int> pii;
inline ll read(){ll x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;}
inline ll qpow(ll a,ll b,ll p){ll ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
inline void gmin(int &a,int b){if(b<a)a=b;}inline void gmin(ll &a,ll b){if(b<a)a=b;}
inline void gmax(int &a,int b){if(b>a)a=b;}inline void gmax(ll &a,ll b){if(b>a)a=b;}
inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
inline ll max(ll a,ll b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
const int N = 205,M = 5005,mod=1e9+7;
int n,m,s,t;
struct edge{int to,nxt;ll dis;edge(int to=0,int nxt=0,ll dis=0):to(to),nxt(nxt),dis(dis){}}e[M*2];int head[N],cnt=1;
void adde(int u,int v,int w){e[++cnt]=edge(v,head[u],w);head[u]=cnt;}
int d[N],now[N];
queue<int> q;
bool bfs()
{
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
q.push(s);d[s]=1;now[s] = head[s];
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = head[u];i;i = e[i].nxt)
{
int v = e[i].to;ll w = e[i].dis;
if(w && !d[v])
{
q.push(v);now[v] = head[v];d[v] = d[u]+1;
if(v == t) return 1;
}
}
}
return 0;
}
ll dinic(int u,ll flow)
{
if(u == t) return flow;
ll rest = flow,i;
for(i = now[u];i;i = e[i].nxt)
{
int v = e[i].to;ll w = e[i].dis;
if(w && d[v] == d[u]+1)
{
ll fl = dinic(v,min(w,rest));
if(!fl) d[v] = 0;
e[i].dis -= fl;e[i^1].dis += fl;
rest -= fl;
}
if(!rest) break;
}
now[u] = i;
return flow - rest;
}
inline void solve()
{
cin >> n >> m >> s >> t;
rfor(i,1,m)
{
int u,v,w;
cin >> u >> v >> w;
adde(u,v,w);
adde(v,u,0);
}
ll flow = 0,ans = 0;
while(bfs())
{
do
{
flow = dinic(s,1e18);
ans += flow;
}while(flow);
}
cout << ans;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;//cin >> t;
while(t--) solve();
return 0;
}
Details
answer.code:90:2: error: stray ‘#’ in program
90 | }#include <bits/stdc++.h>
| ^
answer.code:90:3: error: ‘include’ does not name a type
90 | }#include <bits/stdc++.h>
| ^~~~~~~
answer.code:99:11: error: redefinition of ‘ll read()’
99 | inline ll read(){ll x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;}
| ^~~~
answer.code:10:11: note: ‘ll read()’ previously defined here
10 | inline ll read(){ll x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;}
| ^~~~
answer.code:100:11: error: redefinition of ‘ll qpow(ll, ll, ll)’
100 | inline ll qpow(ll a,ll b,ll p){ll ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
| ^~~~
answer.code:11:11: note: ‘ll qpow(ll, ll, ll)’ previously defined here
11 | inline ll qpow(ll a,ll b,ll p){ll ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
| ^~~~
answer.code:101:13: error: redefinition of ‘void gmin(int&, int)’
101 | inline void gmin(int &a,int b){if(b<a)a=b;}inline void gmin(ll &a,ll b){if(b<a)a=b;}
| ^~~~
answer.code:12:13: note: ‘void gmin(int&, int)’ previously defined here
12 | inline void gmin(int &a,int b){if(b<a)a=b;}inline void gmin(ll &a,ll b){if(b<a)a=b;}
| ^~~~
answer.code:101:56: error: redefinition of ‘void gmin(ll&, ll)’
101 | inline void gmin(int &a,int b){if(b<a)a=b;}inline void gmin(ll &a,ll b){if(b<a)a=b;}
| ^~~~
answer.code:12:56: note: ‘void gmin(ll&, ll)’ previously defined here
12 | inline void gmin(int &a,int b){if(b<a)a=b;}inline void gmin(ll &a,ll b){if(b<a)a=b;}
| ^~~~
answer.code:102:13: error: redefinition of ‘void gmax(int&, int)’
102 | inline void gmax(int &a,int b){if(b>a)a=b;}inline void gmax(ll &a,ll b){if(b>a)a=b;}
| ^~~~
answer.code:13:13: note: ‘void gmax(int&, int)’ previously defined here
13 | inline void gmax(int &a,int b){if(b>a)a=b;}inline void gmax(ll &a,ll b){if(b>a)a=b;}
| ^~~~
answer.code:102:56: error: redefinition of ‘void gmax(ll&, ll)’
102 | inline void gmax(int &a,int b){if(b>a)a=b;}inline void gmax(ll &a,ll b){if(b>a)a=b;}
| ^~~~
answer.code:13:56: note: ‘void gmax(ll&, ll)’ previously defined here
13 | inline void gmax(int &a,int b){if(b>a)a=b;}inline void gmax(ll &a,ll b){if(b>a)a=b;}
| ^~~~
answer.code:103:12: error: redefinition of ‘int max(int, int)’
103 | inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
| ^~~
answer.code:14:12: note: ‘int max(int, int)’ previously defined here
14 | inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
| ^~~
answer.code:103:56: error: redefinition of ‘int min(int, int)’
103 | inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
| ^~~
answer.code:14:56: note: ‘int min(int, int)’ previously defined here
14 | inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
| ^~~
answer.code:104:11: error: redefinition of ‘ll max(ll, ll)’
104 | inline ll max(ll a,ll b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
| ^~~
answer.code:15:11: note: ‘ll max(ll, ll)’ previously defined here
15 | inline ll max(ll a,ll b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
| ^~~
answer.code:104:52: error: redefinition of ‘ll min(ll, ll)’
104 | inline ll max(ll a,ll b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
| ^~~
answer.code:15:52: note: ‘ll min(ll, ll)’ previously defined here
15 | inline ll max(ll a,ll b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}
| ^~~
answer.code:105:11: error: redefinition of ‘const int N’
105 | const int N = 205,M = 5005,mod=1e9+7;
| ^
answer.code:16:11: note: ‘const int N’ previously defined here
16 | const int N = 205,M = 5005,mod=1e9+7;
| ^
answer.code:105:19: error: redefinition of ‘const int M’
105 | const int N = 205,M = 5005,mod=1e9+7;
| ^
answer.code:16:19: note: ‘const int M’ previously defined here
16 | const int N = 205,M = 5005,mod=1e9+7;
| ^
answer.code:105:28: error: redefinition of ‘const int mod’
105 | const int N = 205,M = 5005,mod=1e9+7;
| ...