#include<iostream>
#include<fstream>
using namespace std;
const int MAX = 100;
struct{
int n;
int adjvex[MAX];
int weight[MAX];
}Edge[MAX];
int f[MAX][MAX],c[MAX][MAX],cf[MAX][MAX],father[MAX];
bool vs[MAX];
void DFS(int cur,int n);
int GetMinCf(int t);
int FordFulkerson(int s,int t,int n);
int main(void){
int n,e,a,b,s,t;
int i,j;
ifstream in("data.in");
ofstream out("data.out");
in>>n>>e;
for(i=0;i<=n+1;i++)
Edge[i].n = 0;
s = 0;
t = ++n;
memset(c,0,sizeof(c) );
for(i=0;i<e;i++){
in>>a>>b;
Edge[a].adjvex[ Edge[a].n ] = b;
Edge[a].weight[ Edge[a].n++ ] = 1;
Edge[b].adjvex[ Edge[b].n ] = t;
Edge[b].weight[ Edge[b].n++ ] = 1;
Edge[s].adjvex[ Edge[s].n ] = a;
Edge[s].weight[ Edge[s].n++ ] = 1;
c[a][b] = c[s][a] = c[b][t] = 1;
}
out<<FordFulkerson(s,t,n)<<endl;
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
if(f[i][j])
out<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl;
system("pause");
return 0;
}
int FordFulkerson(int s,int t,int n){
int i,j,inc,flow;
for(i=0;i<=n;i++)
for(j=0;j<=n;j++){
f[i][j] = 0;
cf[i][j] = c[i][j]-f[i][j];
}
flow = 0;
memset(father,0,sizeof(father) );
memset(vs,0,sizeof(vs) );
DFS(s,n);
while(father[t]){
inc = GetMinCf(t);
flow += inc;
for(i=t;i!=s;i=father[i]){
f[father[i] ][i] += inc;
f[i][father[i] ] = -f[father[i] ][i];
cf[father[i] ][i] -= inc;
cf[i][father[i] ] += inc;
}
memset(vs,0,sizeof(vs) );
memset(father,0,sizeof(father) );
DFS(s,n);
}
return flow;
}
int GetMinCf(int t){
int r;
r = cf[father[t] ][t];
for(int i=father[t];father[i];i=father[i])
if(cf[father[i] ][i]<r)
r = cf[father[i] ][i];
return r;
}
void DFS(int cur,int n){
int i,v;
vs[cur] = true;
for(i=0;i<=n;i++)
if(!vs[i]&&cf[cur][i]>0){
father[i] = cur;
DFS(i,n);
}
}
|