#include<cstdio>
#include<iostream>
using namespace std;

#define MAXN 100
#define inf 1000000000

int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
	int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
	if (source==sink) return inf;
	for (i=0;i<n;i++)
		for (j=0;j<n;flow[i][j++]=0);
	for (;;){
		for (i=0;i<n;pre[i++]=0);
		pre[t=source]=source+1,d[t]=inf;
		for (p=q=0;p<=q&&!pre[sink];t=que[p++])
			for (i=0;i<n;i++)
				if (!pre[i]&&j==mat[t][i]-flow[t][i])
					pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
				else if (!pre[i]&&j==flow[i][t])
					pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
		if (!pre[sink]) break;
		for (i=sink;i!=source;)
			if (pre[i]>0)
				flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
			else
				flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
	}
	for (j=i=0;i<n;j+=flow[source][i++]);
	return j;
}


int main(){
  int n;//point
  int m;//arc
  int i,j;
  int mat[MAXN][MAXN];
  int flow[MAXN][MAXN];
  freopen("G://CBFiles//Files//in.txt","r",stdin);
  freopen("G://CBFiles//Files//out.txt","w",stdout);
  while(scanf("%d%d",&m,&n)!=EOF){
    for(i=0;i<m;i++){
      int s,e,v;
      scanf("%d%d%d",&s,&e,&v);
      mat[s-1][e-1]+=v;
      mat[e-1][s-1]=mat[s-1][e-1];
    }
    for(i=0;i<n;i++){
       for(j=0;j<n;j++){
          cout<<"mat["<<i+1<<"]["<<j+1<<"] "<<mat[i][j]<<"    ";
        }
        cout<<endl;
    }
    int res=max_flow(n,mat,0,n-1,flow);
    cout<<res<<endl;

  }

}

• Re:查的一个网络流的dinic模板,浙大的,但是貌似不管用啊,返回的结果是0...哪位大牛进来帮帮忙??? (33) zhu4800448 2010-08-23 14:47:47
• Re:查的一个网络流的dinic模板,浙大的,但是貌似不管用啊,返回的结果是0...哪位大牛进来帮帮忙??? (1599) 851540201 2011-02-15 11:19:39