//思路
//添加两个超级源s,超级汇t
//　　如果某个节点(i)的输入部分不含1，则添加一条s->i路径，容量为Qi;
//　　如果某个节点(j)输出全为1，则添加一条j->t路径，容量为Qj;
//　　如果节点i的输出与j的输入不存在冲突(输出与输入对应位置的和不能为1)，则添加一条i->j的路径，容量为min(Qi, Qj).


#include<iostream>
using namespace std;

const int inf=10001;
int s=0; //超级源
int t;   //超级汇

int n;  //机器数
int p;  //每台机器的部分数
int cap[52][52];  //弧(i,j)的容量
int flow[52][52];  //弧(i,j)的流量
bool mark[52][52]={false};  
int sum=0;
bool vist[52];   //标记点i是否已标号

class info   //当前点j的标记信息
{
public:
	int pre;  //当前点j的前驱i
	int lv;  //l(v)
	int q;  //机器（结点i）的生产量（容量）
	int in[10];  //输入规格
	int out[10]; //输出规格
	int nei[51];  //当前结点直接指向的邻居结点
	int pn;  //邻居结点的指针
}node[52];

int min(int a,int b)
{
	return a<b?a:b;
}

void back(void)
{
	int x=t;
	while(x!=s)
	{
		if(x!=t && node[x].pre!=s)
		{
			if(!mark[ node[x].pre ][x])
				sum++;           //记录流量发生变化的弧数（含s、t的弧除外）
			mark[ node[x].pre ][x]=true;  //标记弧(i,j)的流量是否发生了变化（含s、t的弧除外）
		}
		flow[ node[x].pre ][x] += node[t].lv;  //改进增广路
		x=node[x].pre;

	}
	return;
}

bool bfs(void)
{
	memset(vist,false,sizeof(vist));
	vist[s]=true;

	int queue[52];
	int head=0;
	int tail=0;
	queue[tail++]=s;

	while(head<=tail-1)  //再也找不到增广路的结束条件
	{
		int x=queue[head];
		int y;
		for(int i=0;i<node[x].pn;i++)
		{
			y=node[x].nei[i];
			if(!vist[y] && flow[x][y]<cap[x][y])   //搜索的目标要求是 未标记 & 非饱和弧
			{
				queue[tail++]=y;

				vist[y]=true;
				node[y].pre=x;
				node[y].lv=min( node[x].lv , cap[x][y]-flow[x][y] );
			}
			if(vist[t])  //当超级汇被标记
				break;
		}
		if(!vist[t])
			head++;
		else
			return true;  //搜索到一条增广路
	}
	return false;
}

int main(int i,int j,int k)
{
	//freopen("in.txt","r",stdin);

	/*Input*/

	cin>>p>>n;

	/*Initial*/

	node[s].pre=-1;
	node[s].lv=inf;
	t=n+1;
	for(i=0;i<t;i++)
		node[i].pn=0;

	/*Input & Structure Graphs*/

	bool sign;
	for(i=1;i<=n;i++)
	{
		sign=false;
		cin>>node[i].q;

		for(j=0;j<p;j++)
		{
			cin>>node[i].in[j];
			if(node[i].in[j]==1)  //如果某个节点(i)的输入部分不含1
				sign=true;
		}
		if(!sign)   //则添加一条s->i路径，容量为Qi
		{
			node[s].nei[ node[s].pn++ ]=i;
			cap[s][i]=node[i].q;
			flow[s][i]=0;
		}

		sign=false;
		for(j=0;j<p;j++)
		{
			cin>>node[i].out[j];
			if(node[i].out[j]==0)  //如果某个节点(j)输出全为1
				sign=true;
		}
		if(!sign)  //则添加一条j->t路径，容量为Qj
		{
			node[i].nei[ node[i].pn++ ]=t;
			cap[i][t]=node[i].q;
			flow[i][t]=0;
		}
	}

	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			sign=false;
			if(i!=j)
			{
				for(k=0;k<p;k++)
					if((node[i].out[k] + node[j].in[k])==1)  //如果节点i的输出与j的输入不存在冲突
					{                                      //即输出与输入对应位置的和不为1
						sign=true;
						break;
					}

				if(!sign)        //则添加一条i->j的路径，容量为min(Qi, Qj).
				{
					node[i].nei[ node[i].pn++ ]=j;
					cap[i][j]=min(node[i].q,node[j].q);
					flow[i][j]=0;
				}
			}
		}

	/*标号法找增广轨*/

	while(true)
	{
		if(bfs())  //如果能搜到到增广路
			back();  //从超级汇开始回溯,改进增广路
		else
		{
			int max=0;
			for(i=0;i<node[s].pn;i++)
				max+=flow[s][ node[s].nei[i] ];
			cout<<max<<' '<<sum<<endl;
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
					if(i!=j && mark[i][j])
						cout<<i<<' '<<j<<' '<<flow[i][j]<<endl;
			break;
		}
	}
	return 0;
}

• Re:这是我POJ3436的代码，不是拆点做的。怎样也发现不了问题，测试了N个例子了，牛人帮我看看 (114) 455462586 2011-11-18 23:20:57