poj 3436 ACM Computer Factory(最大流)

轉：

有N台機器，每台機器有P部分，每部分都有各自的輸入、輸出規格，因此一台機器有P個輸入規格，P個輸出規格。每台機器有2*P+1種參數去描述：第一個參數Q：該機器的容量；接下來P個參數S：該機器各部分的輸入規格；接下來P個參數D：該機器各部分的輸出規格。

其中輸入規格有三種情況：0,1,2

0：該部分不能存在

1：該部分必須保留

2：該部分可有可無

輸出規格有2種情況：0,1

0：該部分不存在

1：該部分存在

注意：本題可以只有一次輸入，一次輸出，還有Sample I/O這段英文不用輸入輸出

Sample input:

P N （N台機器，每台機器有P部分）

接著輸入N行，其實每行都是一個結點的信息

每一行的格式為 一個Q P個S P個D

其中Q為當前結點的容量，S都是當前結點的輸入規格，D都是輸出規格

Sample output:

第一行的兩個數字分別表示：最大流的值，流量發生變化的邊數M（和s還有t關聯的邊不在其內，那些不屬於原有的邊，是附加邊）

接下來有M行，每一行都有三個數字，A B W

A B為流量發生變化的邊的端點，W為流量的變化值（每條邊初始流量為0，最終流量就是找到最大流時的流量）

若圖不連通，則輸出0 0

解題思路:

首先構造圖：

添加兩個超級源s,超級匯t

　　如果某個節點(i)的輸入部分不含1，則添加一條s->i路徑，容量為Qi;

　　如果某個節點(j)輸出全為1，則添加一條j->t路徑，容量為Qj;

　　如果節點i的輸出與j的輸入不存在沖突(輸出與輸入對應位置的和不能為1)，則添加一條i->j的路徑，容量為min(Qi, Qj).

PS：輸出與輸入對應位置的和不能為1，就是說組合為可以為00，11， 21或20，但不能是01

解題方法：

就是最大流問題

#include 
#include 
#include 
#include 
using namespace std;

const int INF = 0x3f3f3f3f;
int n,p;
int in[55][25];
int s,t;
int cap[55][55],tmp[55][55];
int pre[55];

int maxflow()
{
	int flow = 0;
	queue que;
	for(;;)
	{
		memset(pre,-1,sizeof(pre));
		while(!que.empty()) que.pop();

		que.push(s);
		while(!que.empty())
		{
			int u = que.front();
			que.pop();
			for(int i = 0; i <= n+1; i++)
			{
				if(cap[u][i] && pre[i] == -1)
				{
					pre[i] = u;
					que.push(i);
				}
			}
		}

		if(pre[t] == -1) break;

		int minflow = INF;
		for(int u = t; u != s; u = pre[u])
		{
			if(minflow > cap[pre[u]][u])
				minflow = cap[pre[u]][u];
		}

		for(int u = t; u != s; u = pre[u])
		{
			cap[pre[u]][u] -= minflow;
			cap[u][pre[u]] += minflow;
		}
	
		flow += minflow;
	}
	return flow;
}

int main()
{
	while(~scanf("%d %d",&p,&n))
	{
		for(int i = 1; i <= n; i++)
		{
			scanf("%d",&in[i][0]);
			for(int j = 1; j <= p+p; j++)
				scanf("%d",&in[i][j]);
		}
		memset(cap,0,sizeof(cap));
		s = 0;
		t = n+1;

		for(int i = 1; i <= n; i++)
		{
			bool flag = true;
			for(int j = 1; j <= p; j++)
			{
				if(in[i][j] == 1)
				{
					flag = false;
					break;
				}
			}
			if(flag)
				cap[s][i] = in[i][0];

			flag = true;
			for(int j = p+1; j <= p+p; j++)
			{
				if(in[i][j] == 0)
				{
					flag = false;
					break;
				}
			}
			if(flag)
				cap[i][t] = in[i][0];


			for(int j = 1; j <= n; j++)
			{
				if(i != j)
				{
					flag = true;
					for(int k = 1; k <= p; k++)
					{
						if(in[i][k+p]+in[j][k] == 1)
						{
							flag = false;
							break;
						}
					}
					if(flag)
						cap[i][j] = min(in[i][0], in[j][0]);
				}
			}
		}

		memcpy(tmp,cap,sizeof(cap));
		int flow = maxflow();

		int out[55][5];
		int cnt = 0;
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				if(i != j && cap[i][j] < tmp[i][j])
				{
					out[cnt][0] = i;
					out[cnt][1] = j;
					out[cnt][2] = tmp[i][j]-cap[i][j];
					cnt++;
				}
			}
		}

		printf("%d %d\n",flow,cnt);
		for(int i = 0; i < cnt; i++)
		{
			printf("%d %d %d\n",out[i][0],out[i][1],out[i][2]);
		}
	}
	return 0;
}