题目
http://poj.org/problem?id=3436
题意
有一条生产线，生产的产品共有p个(p<=10)零件，生产线上共有n台(n<=50)机器，每台机器可以每小时加工Qi个产品，但有输入要求，即对于部件Pi，输入要求会说明要求其存在(1)，不存在(0)或者无要求(2)，每台机器的输出状态是一定的，会说明经过该机器加工后某个零件是否存在(1)，不存在(0)。所有零件都存在(状态都为1时)组装成功，问如何重新安排生产线这张图使得每小时输出的产品数量最多？或者可以简单理解为：在有向图中有n个结点，它们有允许的状态输入，有确定的状态输出，每个点有自身容量限制，状态输入全为0的结点都为最大流起点，状态输出全为1的结点都为最大流终点，求最大流容量。
思路
题目索引中这道题可以使用KM算法，但是我采用了较为简单的思路。
首先对于某两个机器结点i,j，从i出发能否连接j可以直接穷举j的输入状态是否符合i的输出状态。
这样就能得到初始的图，而在这张图中，由于作为起点或终点的结点可能有很多个，所以需要建立超级起点，从超级起点出发连接所有起点，建立超级终点，从所有终点出发连接超级终点。
但是此时这张图上只有点有流量限制，边没有流量限制，所以需要把机器结点拆分为两个结点，两个结点一个为入点，一个为出点，入点到出点之间连一条有向边，容量限制为点的流量限制，这样就能够简单运用最大流算法处理这个问题。注意此时原先从这个机器节点出发的所有边都改从出点出发，所有到这个机器节点的弧都改为从入点到达。
感想
这道题题目清晰，注意可能是多组数据。是最大流入门的好题。
很久没有做题了，打算重拾这个习惯，代码中的最大流是根据记忆重现的，可能效率不太高。
代码
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iostream>
#include <assert.h>
#include <sstream>
#include <cctype>
#include <queue>
#include <stack>
#include <map>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld; const int maxp = 10;
const int maxn = 104;
const int maxm = 11000;
const int inf = 0x3ffffff; int p,n; int input[maxn][maxp];
int output[maxn][maxp];
int v[maxn]; int oldg[maxn][maxn];
int ogn[maxn]; int first[maxn];
struct edge
{
int nxt, to, fromId, toId, c;
} g[maxm];
int gn; bool vis[maxn]; bool matchIn(int prev, int nxt)
{
for(int i = 0; i < p; i++)
{
int sNxt = nxt>n?1:input[nxt][i];
int sPrev = nxt?output[prev][i]:0;
if(sNxt != 2 && sNxt != sPrev)return false;
}
return true;
} void genOldGraph()
{
for(int i = 0; i <= n; i++)
{
for(int j = 1; j <= n+1; j++)
{
if(i != j && matchIn(i, j))
{
oldg[i][ogn[i]++] = j;
}
}
}
} bool testConnect(int s)
{
if(s == n + 1)return true;
vis[s] = true;
for(int i = 0; i < ogn[s]; i++)
{
if(!vis[oldg[s][i]])
if(testConnect(oldg[s][i]))return true;
}
return false;
} inline int inId(int f)
{
return (f?(f<=n?2*f:(2*f-1)):0);
} inline int outId(int t)
{
return (t?(2 * t - 1):0);
} void addEdge(int fId, int tId)
{
// n+1->2n+1, 0->0, 1...n->(1,2),(3,4),(5,6)...(2n-1,2n)
int f = fId==tId?outId(fId):inId(fId);
int t = fId==tId?inId(fId):outId(tId);
int c = fId==tId?v[fId]:inf;
g[gn].nxt = first[f];
g[gn].fromId = fId;
g[gn].toId = tId;
g[gn].c = c;
g[gn].to = t;
first[f] = gn;
gn++;
g[gn].nxt = first[t];
g[gn].fromId = tId;
g[gn].toId = fId;
g[gn].c = 0;
g[gn].to = f;
first[t] = gn;
gn++;
// printf("%d to %d(%d to %d): %d\n",fId, tId, f, t, c);
} bool genNewGraph()
{
if(!testConnect(0))return false;
for(int i = 0; i <= n + 1; i++)
{
for(int j = 0; j < ogn[i]; j++)
{
addEdge(i, oldg[i][j]);
}
}
for(int i = 1; i <= n; i++)
{
addEdge(i,i);
}
memset(vis,false,sizeof vis);
return true;
} int maxflowsub(int s, int f, int flow){
if(s == 2 * n + 1)return flow;
int ans = 0;
vis[s] = true;
for(int p = first[s];p != -1;p=g[p].nxt){
if(g[p].to == f || g[p].c == 0)continue;
int t = g[p].to;
if(!vis[t] && (ans = maxflowsub(t, s, min(flow, g[p].c)))){
g[p].c -= ans;
g[p^1].c += ans;
return ans;
}
}
return 0;
} int maxflow()
{
int ans = 0;
int sub = 0;
while((sub = maxflowsub(0, -1, inf))){
ans += sub;
memset(vis,false,sizeof vis);
}
return ans;
} void genResult(int ans){
int m = 0;
for(int i = 0;i < gn;i+=2){
if(g[i].fromId && g[i].toId <= n && g[i].fromId != g[i].toId && g[i].c < inf){
m++;
}
}
printf("%d %d\n", ans, m);
for(int i = 0;i < gn;i+=2){
if(g[i].fromId && g[i].toId <= n && g[i].fromId != g[i].toId && g[i].c < inf){
printf("%d %d %d\n", g[i].fromId, g[i].toId, g[i + 1].c);
}
}
} void init()
{
for(int i = 1; i <= n; i++)
{
scanf("%d", v + i);
for(int j = 0; j < p; j++)
{
scanf("%d", input[i] + j);
}
for(int j = 0; j < p; j++)
{
scanf("%d", output[i] + j);
}
}
memset(ogn, 0, sizeof ogn);
memset(vis, false, sizeof vis);
memset(first, -1, sizeof first);
gn = 0;
} void solve(){
genOldGraph();
if(!genNewGraph()){
puts("0 0");
}else{
int ans = maxflow();
genResult(ans);
}
} int main()
{
while(scanf("%d%d",&p, &n) == 2)
{
init();
solve();
}
return 0;
}