QAQ和标程对拍了,没有错QAQ
by C201914 @ 2018-08-10 19:52:20
补:DINIC遭遇相同
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define BFS BreadFirstSearch
#define DFS DarkFlameS
#define INF 0x7ffffff
#define MAXN 300000
using namespace std;
int n,m,num,h[300001],cnt=0,d[300001],q[300001];
struct fff{
int next;
int to;
int w;
}edge[6000001];
void add(int x,int y,int c)
{
edge[cnt].next=h[x];
edge[cnt].to=y;
edge[cnt].w=c;
h[x]=cnt++;
}
long long read()
{
int bj=1,res=0;char c=0;
while(c<'0'||c>'9'){if(c=='-')bj=-1;c=getchar();}
while(c>='0'&&c<='9'){res=res*10+c-48;c=getchar();}
return bj*res;
}
int BFS(int s,int t)
{
memset(d,0,sizeof(d));
d[s]=1;
int head=0,tail=1;
q[tail]=s;
while(head!=tail)
{
head=(head+1)%MAXN;
int u=q[head];
if(u==t)return 1;
for(int i=h[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(!d[v]&&edge[i].w)
{
d[v]=d[u]+1;
tail=(tail+1)%MAXN;
q[tail]=v;
}
}
}
if(!d[t])return 0;
return 1;
}
int DarkFlameS(int u,int maxf,int t)
{
if(u==t)return maxf;
int res=0;
for(int i=h[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(d[u]+1==d[v]&&edge[i].w)
{
int minn=min(maxf-res,edge[i].w);
int f=DFS(v,minn,t);
edge[i].w-=f;
edge[i^1].w+=f;
res+=f;
if(res>=maxf)return res;
}
}
return res;
}
int Dinic(int s,int t)
{
int ans=0;
while(BFS(s,t))ans+=DFS(s,INF,t);
return ans;
}
int main()
{
// freopen("t1.in","r",stdin);
// freopen("t1.out","w",stdout);
int x,y,c;
memset(h,-1,sizeof(h));
n=read();m=read();num=read();
for(int i=1;i<=m;i++)
{
x=read();y=read();c=read();
add(x,y,c);
add(y,x,0);
}
int ans=Dinic(1,n);
if(ans==0)printf("Orz Ni Jinan Saint Cow!");
else printf("%d %d",ans,(num+ans-1)/ans);
return 0;
}
```
by C201914 @ 2018-08-13 15:57:45