4692082_ce.cpp

部分PKU上的源码

#include<iostream>
#define MAX 1000000
using namespace std;
int n,np,nc,nb,m;
char input;
int map[105][105];//0为超级s，n+1为超级T
int cf[105][105];
int prev[105],dis[105];
bool used[105];
int all;
int findmin()
{
	int min=MAX-10,re=-1;
	for(int count=0;count<=n+1;count++)
	{
		if(min>dis[count]&&used[count]==false)
		{
			min=dis[count];
			re=count;
		}
	}
	return re;
}
bool dj()
{
	memset(used,false,sizeof(used));
	int i,j;
	for(i=0;i<=n+1;i++)
	{
		for(j=0;j<=n+1;j++)
		{
			if(map[i][j]!=0) cf[i][j]=map[i][j];
			else cf[i][j]=MAX;
		}
	}
	for(int count=0;count<=n+1;count++)
	{
		dis[count]=MAX;
		prev[count]=-1;
	}
	dis[0]=0;prev[0]=0;
	while(1)
	{ 
		int temp=findmin();
		if(temp==-1) break;
		used[temp]=true;
		for(j=0;j<=n+1;j++)
		{
			if(dis[j]>dis[temp]+cf[temp][j]) 
			{
				dis[j]=dis[temp]+cf[temp][j];
				prev[j]=temp;
			}
		}
		if(temp==n+1) break;
	}
	if(dis[n+1]!=MAX) return true;
	else return false;
}
void ek()
{
	all=0;
	while(dj())
	{
		int i;
		i=n+1;
		int min=MAX;
		while(i)
		{
			if(map[prev[i]][i]<min) min=map[prev[i]][i];
			i=prev[i];
		}
		i=n+1;
		while(i)
		{
			map[prev[i]][i]-=min;
			map[i][prev[i]]+=min;
			i=prev[i];
		}
		all+=min;
	}
	cout<<all<<endl;
}

int main()
{
	while(cin>>n)
	{
		cin>>np>>nc>>m;
		nb=n-np-nc;
		memset(map,0,sizeof(map));
		int count;
		for(count=1;count<=m;count++)
		{
			int t1,t2,t3;
			cin>>input>>t1>>input>>t2>>input>>t3;
			map[t1+1][t2+1]=t3;
		}
		for(count=1;count<=np;count++)
		{
			int t1,t2;
			cin>>input>>t1>>input>>t2;
			map[0][t1+1]=t2;
		}
		for(count=1;count<=nc;count++)
		{
			int t1,t2;
			cin>>input>>t1>>input>>t2;
			map[t1+1][n+1]=t2;
		}
		ek();
	}
	return 0;
}
//改为前流推进