题目大意

    生产电脑的工厂将一台电脑分成P个部件来进行流水线生产组装，有N个生产车间，每个车间可以将一个半成品电脑添加某些部件，使之成为另一个半成品电脑或者成为一台完好的电脑，且每个车间有一个效率，即在单位时间内可以将K个半成品组装为另外K个半成品或者完好的电脑。每个车间在组装完成之后，都将组装后的半成品送到另外一个车间，成品直接送到成品区。 

    现在给出这N个车间的组装原部件集合以及组装后的部件集合（其中 in[1,2,3...p]中 in[i]表示第i种组装元部件，out[1,2,3...p]中out[i]表示第i种组装后的部件。且in[i] = 0表示元部件集合中必须没有第i种部件，in[i]=1表示元部件集合中必须有第i种部件，in[i] = 2表示元部件集合中第i种部件可有可无；out[i]=0表示组装后的部件集合中没有第i种部件，out[i]=1表示组装后的集合中有第i种部件），以及组装效率。求怎样合理的分配N个车间之间的流量，使得组装效率最大。

题目分析

    在本题中的最大效率，可以视为各个车间构成的网络图的最大流量。那么，如何构造网络流图求出最大流量呢？ 

    首先考虑将每个车间视为一个节点，若车间A的组装后的部件集合可以被车间B接受，那么单向连接车间A和B。但是，若车间A连接了车间B和车间C，那么A->B和A->C之间的路径容量无法控制。所以这种建图方式不好。 

    再考虑将每个车间拆分为两个节点，一个入节点，表示车间的组装原部件集合，一个出节点，表示车间组装后的部件集合，在入节点和出节点之间用一条容量为K的路径连接起来。若车间A的组装后部件集合可以被车间B的组装原部件集合所接受，那么连接车间A的出节点和车间B的入节点，同时，容量设为无穷大，这是因为车间的效率受其原部件-->组装后部件的组装效率决定，即车间的入节点到出节点的容量决定。 

    在构造好的图上从源点到汇点找最大流量，即为最大效率。

实现

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MAX_NODE 150#define MAX_EDGE_NUM 300#define INFINITE 1 << 25#define min(a, b) a
         
          & p){		return from == p.first && to == p.second;	}};Edge gEdges[MAX_EDGE_NUM];int gEdgeCount;int gFlow[MAX_NODE][MAX_NODE];int gGap[MAX_NODE];int gDist[MAX_NODE];int gHead[MAX_NODE];int gPre[MAX_NODE];int gPath[MAX_NODE];int gSource, gDestination;void InsertEdge(int u, int v, int w){	Edge* it = find(gEdges, gEdges + gEdgeCount, pair
          
           (u, v)); if (it != gEdges + gEdgeCount){ it->w = w; } else{ int e1 = gEdgeCount; gEdges[e1].from = u; gEdges[e1].to = v; gEdges[e1].w = w; gEdges[e1].next = gHead[u]; gHead[u] = e1; gEdgeCount++; int e2 = gEdgeCount; gEdges[e2].from = v; gEdges[e2].to = u; gEdges[e2].w = 0; gEdges[e2].next = gHead[v]; gHead[v] = e2; gEdges[e1].rev = e2; gEdges[e2].rev = e1; gEdgeCount++; }}void Bfs(){ memset(gGap, 0, sizeof(gGap)); memset(gDist, -1, sizeof(gDist)); gGap[0] = 1; gDist[gDestination] = 0; queue
           
            Q; Q.push(gDestination); while (!Q.empty()){ int n = Q.front(); Q.pop(); for (int e = gHead[n]; e != -1; e = gEdges[e].next){ int v = gEdges[e].to; if (gDist[v] >= 0) continue; gDist[v] = gDist[n] + 1; gGap[gDist[v]] ++; Q.push(v); } }}int ISAP(int n){ // n为节点的数目 Bfs(); int u = gSource; int e, d; int ans = 0; while (gDist[gSource] <= n){ if (u == gDestination){ //增广 int min_flow = INFINITE; for (e = gPath[u]; u != gSource; e = gPath[u = gPre[u]]){ //注意，先u = gPre[u]， 再取 e = gPath[u] min_flow = min(min_flow, gEdges[e].w); } u = gDestination; for (e = gPath[u]; u != gSource; e = gPath[u = gPre[u]]){ gEdges[e].w -= min_flow; gEdges[gEdges[e].rev].w += min_flow; gFlow[gPre[u]][u] += min_flow; } ans += min_flow; } for (e = gHead[u]; e != -1; e = gEdges[e].next){ if (gEdges[e].w > 0 && gDist[u] == gDist[gEdges[e].to] + 1) break; } if (e >= 0){ //向前推进 gPre[gEdges[e].to] = u; //前一个点 gPath[gEdges[e].to] = e;//该点连接的前一个边 u = gEdges[e].to; } else{ d = n; for (e = gHead[u]; e != -1; e = gEdges[e].next){ if (gEdges[e].w > 0) //需要能够走通才行!! d = min(d, gDist[gEdges[e].to]); } if (--gGap[gDist[u]] == 0) //gap优化 break; gDist[u] = d+1; //重标号 ++gGap[gDist[u]]; //更新 gap！！ if (u != gSource) u = gPre[u];//回溯 } } return ans;}struct Node{ int id; int p; int component[12]; bool CanConnect(const Node& node){ for (int i = 0; i < p; i++){ if (component[i] == 0 && node.component[i] == 1 || component[i] == 1 && node.component[i] == 0) return false; } return true; }};Node gNodes[MAX_NODE];void BuildGraph(int n){ for (int i = 2; i <= n + 1; i++){ if (gNodes[1].CanConnect(gNodes[i])) InsertEdge(1, i, INFINITE); } for (int i = n+2; i <= 2*n + 1; i++){ for (int j = 2; j <= n + 1; j++){ if (j + n != i && gNodes[i].CanConnect(gNodes[j])) InsertEdge(i, j, INFINITE); } } for (int i = n + 2; i <= 2 * n + 1; i++){ if (gNodes[i].CanConnect(gNodes[2*n+2])) InsertEdge(i, 2*n+2, INFINITE); }}void print_graph(int n){ for (int u = 1; u <= n; u++){ printf("node %d links to ", u); for (int e = gHead[u]; e != -1; e = gEdges[e].next) printf("%d(flow = %d) ", gEdges[e].to, gEdges[e].w); printf("\n"); }}int main(){ int p, n, w, u, v; while (scanf("%d %d", &p, &n) != EOF){ memset(gFlow, 0, sizeof(gFlow)); memset(gHead, -1, sizeof(gHead)); gEdgeCount = 0; int node_id = 1; //构造源点 gNodes[node_id].p = p; for (int i = 0; i < p; i++){ gNodes[node_id].component[i] = 0; } node_id++; for (int i = 0; i < n; i++){ scanf("%d", &w); u = node_id; gNodes[u].p = p; for (int k = 0; k < p; k++){ scanf("%d", &gNodes[u].component[k]); } v = node_id + n; gNodes[v].p = p; for (int k = 0; k < p; k++){ scanf("%d", &gNodes[v].component[k]); } node_id++; InsertEdge(u, v, w); } node_id = 2 * n + 2; gNodes[node_id].p = p; for (int i = 0; i < p; i++){ //构造汇点 gNodes[node_id].component[i] = 1; } gSource = 1; gDestination = 2 * n + 2; BuildGraph(n);// print_graph(2 * n + 2); int result = ISAP(2 * n + 2); printf("%d", result); int count = 0; vector
            
             
               > edge_vec; for (int i = n + 2; i <= 2 * n + 1; i++){ for (int j = 2; j <= n + 1; j++){ if (i != j + n && gFlow[i][j] > 0){ count++; edge_vec.push_back(pair
              
               (i, j)); } } } printf(" %d\n", count); for (int k = 0; k < count; k ++){ int i = edge_vec[k].first; int j = edge_vec[k].second; printf("%d %d %d\n", i - n - 1, j - 1, gFlow[i][j]); } } return 0;}