地震逃生
题意：
- 每条边有最大容量。但是有多条边。求出数量
需要多少批才能运送完成
思路：
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M=40010;
int n,m,x,cnt=0;
int head[M];
int dis[M];
int cur[M];
struct node
{
int v,w,nxt;
} edge[M];
void add(int x,int y,int w)
{
edge[cnt].v=y;
edge[cnt].w=w;
edge[cnt].nxt=head[x];
head[x]=cnt++;
}
void dataset( )
{
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&x);
int a,b,c;
for(int i=0; i<m; i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,0);
}
}
bool bfs()
{
memset(dis,-1,sizeof(dis));
dis[1]=0;
queue<int>qu;
qu.push(1);
while(!qu.empty( ))
{
int u=qu.front( );
qu.pop( );
for(int i=head[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
if(dis[v]==-1&&edge[i].w)
{
dis[v]=dis[u]+1;
qu.push(v);
}
}
}
return dis[n]!=-1;
}
int dfs(int u,int flo)
{
if(u==n)
{
return flo;
}
int detla=flo;
for(int i=cur[u]; i!=-1; i=edge[i].nxt)
{
cur[u]=edge[i].nxt;
int v=edge[i].v;
if(dis[v]==dis[u]+1&&edge[i].w>0)
{
int d=dfs(v,min(detla,edge[i].w));
edge[i].w-=d;
edge[i^1].w+=d;
detla-=d;
if(detla==0)
{
break;
}
}
}
// for(int i=head[u];i!=-1;i=edge[i].nxt)
// {
// int v=edge[i].v;
// if(dis[v]==dis[u]+1&&edge[i].w>0)
// {
// int d=dfs(v,min(detla,edge[i].w));
// edge[i].w-=d;
// edge[i^1].w+=d;
// detla-=d;
// if(detla==0)
// {
// break;
// }
// }
// }
return flo-detla;
}
int dini( )
{
int ans=0;
while(bfs( ))
{
for(int i=1; i<=n; i++)
{
cur[i]=head[i];
}
ans+=dfs(1,INF);
}
return ans;
}
int main( )
{
dataset( );
int a=dini( );
if(a!=0)
{
if(x%a)
{
printf("%d %d\n",a,x/a+1);
}
else
{
printf("%d %d\n",a,x/a);
}
}
else
{
printf("Orz Ni Jinan Saint Cow!\n");
}
return 0;
}
