注意重边。
EK：
#include<iostream> #include<cstdio> #include<queue> #define min(a,b) a<b?a:b using namespace std; const int N = 201; const int INF = 1000000000; int c[N][N]; //保存图的路径权值,有重边就相加 int flow[N][N]; //flow[][]表示已经统计的流,c[u][i] - flow[u][i]表示残余网络 int min_flow[N]; int pre[N]; int n, m; int max_flow() { memset(flow, 0, sizeof(flow)); //在while()外面初始化，注意 int u; int ans = 0; while (1){//pre[],min_flow[]循环初始化 memset(pre, -1, sizeof(pre)); memset(min_flow, 0, sizeof(min_flow)); queue<int> Q; Q.push(1); min_flow[1] = INF; while (!Q.empty()){ u = Q.front(); Q.pop(); if (u == m)break; for (int i = 2; i <= m; i++){ if(pre[i] < 0 && c[u][i] - flow[u][i] > 0){ pre[i] = u; //保存前驱，同时标记是否已访问 min_flow[i] = min(min_flow[u], c[u][i] - flow[u][i]); Q.push(i); } } } if (pre[m] == -1) break; //无法搜到汇点了，也就是说已经找不到增广路了 for (int v = m; v != 1; v = pre[v]){ //对找到的增广路进行回溯，从而修改残留网络 u = pre[v]; flow[u][v] += min_flow[m]; flow[v][u] -= min_flow[m]; } ans += min_flow[m]; } return ans; } int main() { int x, y, z; while(~scanf("%d%d", &n, &m)){ memset(c, 0, sizeof(c)); for (int i = 0; i < n; i++) { scanf("%d%d%d", &x, &y, &z); c[x][y] += z; } printf("%d\n", max_flow()); } return 0; }DINIC： #include<cstdio> #include<cstring> #include<climits> #include<queue> #define find_min(a,b) a<b?a:b using namespace std; const int N = 201; struct Edge{ int s,e,v,next; }edge[2*N]; int e_num,head[N],d[N],sp,tp; int n,m; void AddEdge(int a,int b,int c){ edge[e_num].s=a; edge[e_num].e=b; edge[e_num].v=c; edge[e_num].next=head[a]; head[a]=e_num++; edge[e_num].s=b; edge[e_num].e=a; edge[e_num].v=0; edge[e_num].next=head[b]; head[b]=e_num++; } void getmap(){ int a,b,c; e_num=0; memset(head,-1,sizeof(head)); for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); AddEdge(a,b,c); } } int bfs(){ queue <int> q; memset(d,-1,sizeof(d)); d[sp]=0; q.push(sp); while(!q.empty()){ int cur=q.front(); q.pop(); for(int i=head[cur];i!=-1;i=edge[i].next){ int u=edge[i].e; if(d[u]==-1 && edge[i].v>0){//没有标记,且可行流大于0 d[u]=d[cur]+1; q.push(u); } } } return d[tp] != -1;//汇点是否成功标号,也就是说是否找到增广路 } int dfs(int a,int b){//a为起点 int r=0; if(a==tp)return b; for(int i=head[a];i!=-1 && r<b;i=edge[i].next){ int u=edge[i].e; if(edge[i].v>0 && d[u]==d[a]+1){ int x=find_min(edge[i].v,b-r); x=dfs(u,x); r+=x; edge[i].v-=x; edge[i^1].v+=x; } } if(!r)d[a]=-2; return r; } void dinic(int sp,int tp){ int total=0,t; while(bfs()){ while(t=dfs(sp,INT_MAX)) total+=t; } printf("%d\n",total); } int main() { while(~scanf("%d%d",&m,&n)){ getmap(); sp=1; tp=n; dinic(sp,tp); } return 0; }
