建图的时候已经把输入 和输出边的点分开了 就是不知道怎么继续了！！求教啊！
#include <iostream>
using namespace std;
const int maxn=60500;
const int inf=1<<30;
struct edge
{
	int from,to,val,next;
}map[maxn];
int vis[500],que[500],dist[500],len;
int wIn[500],wOut[500];
int mark[500];
int S,T;
int M,N;
int edg[5001][2];
void init()
{
	len=0;
	memset(vis,-1,sizeof(vis));
}
void insert (int from,int to,int val)    //从from 到  to
{
	map[len].from=from;
	map[len].to=to;
	map[len].val=val;
	map[len].next=vis[from];
	vis[from]=len++;
	map[len].from=to;
	map[len].to=from;
	map[len].val=0;
	map[len].next=vis[to];
	vis[to]=len++;
}
int Dinic(int n,int s,int t)
{
	int ans=0;
	while(true)
	{
		int head,tail,id,i;
		head=tail=0;
		que[tail++]=s;
		memset(dist,-1,sizeof(dist));
		dist[s]=0;
		while(head<tail)
		{
			id=vis[que[head++]];
			while(id!=-1)
			{
				if(map[id].val>0&&dist[map[id].to]==-1)
				{
					dist[map[id].to]=dist[map[id].from]+1;
					que[tail++]=map[id].to;
					if(map[id].to==t)
					{
						head=tail;
						break;
					}
				}
				id=map[id].next;
			}
		}
		if(dist[t]==-1)
			break;
		id=s,tail=0;
		while(true)
		{
			if(id==t)       //找到一条增广路
			{
				int flow=inf,fir;
				for(i=0;i<tail;i++)
					if(map[que[i]].val<flow)
					{
						fir=i;
						flow=map[que[i]].val;
					}
					for(i=0;i<tail;i++)
						map[que[i]].val-=flow,map[que[i]^1].val+=flow;
					ans+=flow;
					tail=fir;
					id=map[que[fir]].from;
			}
			id=vis[id];
			while(id!=-1)
			{
				if(map[id].val>0&&dist[map[id].from]+1==dist[map[id].to])
					break;
				id=map[id].next;
			}
			if(id!=-1)
			{
				que[tail++]=id;
				id=map[id].to;
			}
			else
			{
				if(tail==0)
					break;
				dist[map[que[tail-1]].to]=-1;
				id=map[que[--tail]].from;
			}
		}
	}
	return ans;
}
void CreatGraph()
{// 建图
	int i, ii;
	S = 0;
	T = 2 * N + 1;
	len = 0;
	for (i = 1; i <= N; i++)
	{
		ii = i + N;
		insert(S, ii, wOut[i]);
		insert(i, T, wIn[i]);
	}
	for (i = 1; i <= M; i++)
	{
		ii = edg[i][0] + N;
		insert(ii, edg[i][1], 0xffffff);
	}
}
int main()
{
	init();
	int i, num;
    int cnt[500];
	scanf("%d%d", &N, &M);
	for (i = 1; i <= N; i++)
		scanf("%d", &wIn[i]);
    for (i = 1; i <= N; i++)
		scanf("%d", &wOut[i]);
    for (i = 1; i <= M; i++)
        scanf("%d%d", &edg[i][0], &edg[i][1]);
	CreatGraph();	
	int ans=Dinic(T,S,T);
	cout<<ans<<endl;
	return 0;
}

• Re:求大牛指点接下来怎么做！ 用dinic模板写的最大流！然后不知道怎么判别输入输出边！ (2754) shenyang_ 2011-10-12 16:04:51