水题
看到oj下面好多人说拆点。但是,我没有拆点却也做出来了。
从网络流的角度都去想没有什么障碍。我们构造出源点s和汇点t
然后看有哪些机器可以和源点连,即input清一色为0或2 连(s,i)cap=Q[i]
看有哪些可以可以与汇点连,即output都为1 连(i,t) cap = Q[i]
然后再看那些机器可以对接,i,j可以对接,即对于j的input,i的output可以满足
注意的是,这里连的边cap=Q[i]
再跑一便最大流就可以了!!!!
代码如下:
#include<iostream> #include<algorithm> #include<queue> using namespace std; typedef pair<int, int> pii; typedef pair<int, pii> pip; const int inf = 2e9; struct edge{ int to, cap, rev, next; }E[10000]; int head[55]; int cnt = 1; void add(int from, int to, int cap,int rev) { E[cnt].to = to;E[cnt].next = head[from]; E[cnt].cap = cap; E[cnt].rev = rev;head[from] = cnt++; } int P, N; int Q[60]; int in[60][15]; int out[60][15]; bool check_ed(int id) { for (int i = 1;i <= P;++i) if (out[id][i] != 1)return false; return true; } bool check_st(int id) { for (int i = 1;i <= P;++i) if (in[id][i] == 1)return false; return true; } bool check_ij(int ma, int mb) { for (int i = 1;i <= P;++i) { if (in[mb][i] == 1 && out[ma][i] == 0)return false; if (in[mb][i] == 0 && out[ma][i] == 1)return false; }return true; } int d[55]; bool searchpath(int s,int t) { fill(d, d + 55, -1); queue<int> que;d[s] = 0; que.push(s); while (!que.empty()) { int u = que.front(); que.pop(); for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (d[e.to] != -1 || e.cap <= 0)continue; d[e.to] = d[u] + 1; que.push(e.to); } }return d[t] != -1; } int matchpath(int u,int t,int f) { if(u == t)return f; for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (d[e.to] <= d[u] || e.cap <= 0)continue; int flow = matchpath(e.to, t, min(f, e.cap)); if (flow > 0) { e.cap -= flow; E[e.rev].cap += flow; return flow; } }return false; } int dinic(int st,int ed) { int flow = 0;int f; while (searchpath(st, ed)) while (f = matchpath(st, ed, inf)) flow += f; return flow; } vector<pip> res; bool vis[55]; void bfs(int s,int t) { res.clear(); fill(vis, vis + 55, false); queue<int> que; que.push(s);vis[s] = true; while (!que.empty()) { int u = que.front(); que.pop();vis[u] = false; for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (e.rev & 1)continue; if (E[e.rev].cap == 0)continue; if (!vis[e.to]) { que.push(e.to); vis[e.to] = true; } if (u != s && e.to != t) res.push_back(make_pair(E[e.rev].cap, make_pair(u, e.to))); } } } int main() { while (scanf("%d %d", &P, &N)!=EOF) { if (P == 0 && N == 0)break; fill(head, head + 55, 0);cnt = 1; for (int i = 1;i <= N;++i) { scanf("%d", &Q[i]); for (int j = 1;j <= P;++j)scanf("%d", &in[i][j]); for (int j = 1;j <= P;++j)scanf("%d", &out[i][j]); }int start = N + 1;int ed = start + 1; for (int i = 1;i <= N;++i) { if (check_st(i)) { add(start, i, Q[i], cnt + 1); add(i, start, 0, cnt - 1); } if (check_ed(i)) { add(i, ed, Q[i], cnt + 1); add(ed, i, 0, cnt - 1); } for (int j = 1;j <= N;++j) { if (j != i && check_ij(i, j)) { add(i, j, Q[i], cnt + 1); add(j, i, 0, cnt - 1); } } }printf("%d ", dinic(start, ed)); bfs(start, ed);printf("%d", res.size()); for (int i = 0;i < res.size();++i) printf("\n%d %d %d", res[i].second.first, res[i].second.second, res[i].first); } }