http://poj.org/problem?id=3436
题意：题意很难懂。给出P N。接下来N行代表N个机器，每一行有2*P+1个数字
第一个数代表容量，第2~P+1个数代表输入，第P+2到2*P+1是代表输出
输入有三种情况，0,1,2.输出有0,1两种情况
输入0代表不能有这个接口，1代表必须要有这个接口，2代表这个接口可有可无。
输出0代表有这个接口，1代表没有这个接口。大概输出就是像插头，输入像插座，只有接口吻合才可以相连。
思路：比较简单的最大流，主要是理解题意很难，把每台机器拆成输入和输出两个点，之间的流量就是第一个数那个流量，然后把符合题意的输入和超级源点相连，把符合题意的输出和超级汇点相连，把符合题意的机器之间的输入输出相连，流量都是INF，用ISAP找到增广路更新的时候，可以顺便记录路径。也可以最后和初始流量比较，如果减少了就说明有流量经过。可是ISAP模板错了导致一直WA了好久，以为是思路错了，用Dinic做过了，这里重新找了份鸟神的模板Orz。
Dinic：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define N 400
const int INF = 0x3f3f3f3f; struct Edge {
int u, v, cap, init;
Edge () {}
Edge (int u, int v, int cap, int init) : u(u), v(v), cap(cap), init(init) {}
}edge[N];
vector<int> G[N];
int cur[N], dis[N], gap[N], pre[N], tot, S, T;
int mp[N][N], info[N][N]; void Add(int u, int v, int cap) {
edge[tot] = Edge(u, v, cap, cap);
G[u].push_back(tot++);
edge[tot] = Edge(v, u, , );
G[v].push_back(tot++);
} int BFS() {
queue<int> que;
while(!que.empty()) que.pop();
memset(dis, INF, sizeof(dis));
dis[S] = ; que.push(S);
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = ; i < G[u].size(); i++) {
Edge& e = edge[G[u][i]];
if(dis[e.v] == INF && e.cap > ) {
dis[e.v] = dis[u] + ;
que.push(e.v);
}
}
}
return dis[T] < INF;
} int DFS(int u, int maxflow) {
if(u == T) return maxflow;
for(int i = cur[u]; i < G[u].size(); i++) {
cur[u] = i; Edge& e = edge[G[u][i]];
if(dis[e.v] == dis[u] + && e.cap > ) {
int flow = DFS(e.v, min(maxflow, e.cap));
if(flow > ) {
e.cap -= flow;
edge[G[u][i] ^ ].cap += flow;
return flow;
}
}
}
return ;
} int Dinic() {
int ans = ;
while(BFS()) {
memset(cur, , sizeof(cur));
int flow;
while(flow = DFS(S, INF)) ans += flow;
}
return ans;
} int main() {
int P, n;
while(~scanf("%d%d", &P, &n)) {
tot = ; S = , T = * n + ;
for(int i = S; i <= T; i++) G[i].clear();
memset(mp, , sizeof(mp));
for(int i = ; i <= n; i++) {
scanf("%d", &info[i][]);
for(int j = ; j <= P; j++)
scanf("%d", &info[i][j]);
for(int j = ; j <= P; j++)
scanf("%d", &info[i][j+P]);
}
for(int i = ; i <= n; i++) {
Add(i, i + n, info[i][]);
int fs = , ft = ;
for(int j = ; j <= P; j++) {
if(info[i][j] == ) fs = ;
if(info[i][j+P] == ) ft = ;
}
if(fs) Add(S, i, INF);
if(ft) Add(i + n, T, INF);
for(int j = ; j <= n; j++) {
if(i == j) continue;
fs = ;
for(int k = ; k <= P; k++)
if(info[i][k+P] != info[j][k] && info[j][k] != )
fs = ;
if(fs) Add(i + n, j, INF);
}
}
int ans = Dinic(), cnt = ;
for(int u = n + ; u <= * n; u++) {
for(int j = ; j < G[u].size(); j++) {
Edge& e = edge[G[u][j]];
if(e.v <= n && e.v > && e.cap < e.init) mp[u-n][e.v] += e.init - e.cap;
}
}
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
if(mp[i][j]) cnt++;
}
}
printf("%d %d\n", ans, cnt);
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
if(mp[i][j]) printf("%d %d %d\n", i, j, mp[i][j]);
}
}
}
return ;
}
ISAP：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define N 400
const int INF = 0x3f3f3f3f; struct Edge {
int v, nxt, cap, init;
}edge[N];
int cur[N], dis[N], gap[N], pre[N], head[N], tot, S, T;
int mp[N][N], info[N][N]; void Add(int u, int v, int cap) {
edge[tot].nxt = head[u]; edge[tot].v = v; edge[tot].cap = cap; edge[tot].init = cap; head[u] = tot++;
edge[tot].nxt = head[v]; edge[tot].v = u; edge[tot].cap = ; edge[tot].init = ; head[v] = tot++;
} int BFS() {
queue<int> que;
while(!que.empty()) que.pop();
memset(dis, -, sizeof(dis));
memset(gap, , sizeof(gap));
que.push(T); dis[T] = ;
gap[] = ;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(~dis[v]) continue;
dis[v] = dis[u] + ;
gap[dis[v]]++;
que.push(v);
}
}
return ~dis[S];
} int ISAP(int n, int m) { // n = T + 1 !!!
memcpy(cur, head, sizeof(cur));
int ans = , i, u = pre[S] = S;
while(dis[S] < n) {
if(u == T) {
int flow = INF, index = S;
for(i = S; i != T; i = edge[cur[i]].v) {
if(flow > edge[cur[i]].cap) {
flow = edge[cur[i]].cap; index = i;
}
}
for(i = S; i != T; i = edge[cur[i]].v) {
edge[cur[i]].cap -= flow; edge[cur[i]^].cap += flow;
int v = edge[cur[i]].v;
if(i > m && v > S && v <= m) {
mp[i-m][v] += flow;
}
}
ans += flow;
u = index;
}
for(i = cur[u]; ~i; i = edge[i].nxt)
if(edge[i].cap > && dis[edge[i].v] + == dis[u])
break;
if(~i) {
cur[u] = i;
pre[edge[i].v] = u;
u = edge[i].v;
} else {
if(--gap[dis[u]] == ) break;
int md = n;
for(i = head[u]; ~i; i = edge[i].nxt) {
if(dis[edge[i].v] < md && edge[i].cap > ) {
md = dis[edge[i].v]; cur[u] = i;
}
}
++gap[dis[u] = md + ];
u = pre[u];
}
}
return ans;
} int main() {
int n, P;
while(~scanf("%d%d", &P ,&n)) {
memset(head, -, sizeof(head));
memset(mp, , sizeof(mp));
tot = ; S = ; T = * n + ;
for(int i = ; i <= n; i++) {
scanf("%d", &info[i][]);
for(int j = ; j <= P; j++)
scanf("%d", &info[i][j]);
for(int j = ; j <= P; j++)
scanf("%d", &info[i][j+P]);
}
for(int i = ; i <= n; i++) {
Add(i, i + n, info[i][]);
int fs = , ft = ;
for(int j = ; j <= P; j++) {
if(info[i][j+P] == ) ft = ;
if(info[i][j] == ) fs = ;
}
if(fs) Add(S, i, INF);
if(ft) Add(i + n, T, INF);
for(int j = ; j <= n; j++) {
fs = ;
for(int k = ; k <= P; k++)
if(info[j][k] != && info[j][k] != info[i][k+P]) fs = ;
if(fs) Add(i + n, j, INF);
}
}
int ans = ISAP(T + , n), cnt = ;
// for(int i = n + 1; i <= 2 * n; i++) {
// for(int j = head[i]; ~j; j = edge[j].nxt) {
// int v = edge[j].v;
// if(v > 0 && v <= n && edge[j].cap < edge[j].init) mp[i-n][v] += edge[j].init - edge[j].cap;
// }
// }
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
if(mp[i][j]) cnt++;
printf("%d %d\n", ans, cnt);
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
if(mp[i][j]) printf("%d %d %d\n", i, j, mp[i][j]);
}
return ;
}