|
发表于 2019-1-27 19:20:46
|
显示全部楼层
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,e[2009][2009],flag=0,top,s[100009],ans,book[100009];
void dfs(int u)
{
if(u==n)
{
top++;
s[top]=n;
int minx=2147483647;
for(int i=1;i<top;i++)
{
if(e[s[i]][s[i+1]]<minx)
{
minx=e[s[i]][s[i+1]];
}
}
ans+=minx;
for(int i=1;i<top;i++)
{
e[s[i]][s[i+1]]-=minx;
e[s[i+1]][s[i]]+=minx;
}
flag=1;
return;
}
if(book[u]==1)
{
return;
}
book[u]=1;
top++;
s[top]=u;
for(int i=0;i<=n;i++)
{
if(e[u][i]>0)
{
dfs(i);
}
}
top--;
return;
}
int main()
{
scanf("%d%d",&n,&m);
n++;
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
e[a][b]+=1;
e[b][n]=1;
e[0][a]=1;
}
while(1>0)
{
memset(book,0,sizeof(book));
flag=0;
top=0;
dfs(0);
if(flag==0)
{
break;
}
}
printf("%d",ans);
return 0;
} |
|