英语不好,直接在网上搜的j嘉哥的题意、、、很详细
题意:电脑工厂有N台机器,每台机器对半成品电脑进行加工。每个电脑由P个部件组成,用0和1表示某部件是否已存在
(1表示存在了)。
每台机器对加工的电脑都是有要求的,只有满足要求,才能进入机器进行加工。
机器对电脑部件的要求用0,1,2表示,输入的P个数中,第i个数为ai,ai=0表示该半成品电脑不能有部件i,ai=1表示
该半成品必须已有部件i(即1),ai=2表示有没有此部件都无关系。
进入机器加工后的电脑出来后所含部件情况用P个数字(0或1)表示。
输入:P和N,接下来N行介绍N个机器,第一个数Q,表示单位时间此机器能加工的电脑数(我是这么理解的),接下来两
个数串,第一个P个数(0,1,2序列)表示该机器的对电脑所含部件的要求,第二个P个数(0,1序列)表示经该机器加工
后,输出的电脑所含部件的情况。
输出:单位时间能生产最多的电脑数,然后输出必须给N台机器间连接的生产线数。每行输出生产线的情况。起点U、终
点V,以及它们的权值W。
以上是嘉哥写的啊,下面我说说:
这个建图有点麻烦啊,得加入超级源点,超级会点啊。。。这个思想以前是没有啊、、以后得记住啊、、每个机器人看做一个接口把满足条件的接口连接在一起、、搜一遍建图啊、、
#include <stdio.h> #include <string.h> #include <queue> #include <iostream> #define N 200 #define oo 1 << 30 using namespace std; struct node { int o, in[20], out[20]; }f[N]; int map[N][N], dp[N][N], v[N], link[N], s[N][3], n; int min(int x, int y) { return x<y?x:y; } int EK() { int sum = 0, i, now, min; queue<int>q; while(1) { memset(v , 0 , sizeof(v));//竟然把sizeof里面的v写成了0还查了好几个小时啊、、呜呜,手残啊 memset(link , -1 , sizeof(link)); while(!q.empty()) q.pop(); q.push(0); v[0] = 1; while(!q.empty()) { now = q.front(); q.pop(); if(now == n+1) break; for(i = 0; i <= n+1; i++) if(!v[i] && map[now][i] > 0) { link[i] = now; v[i] = 1; q.push(i); } } if(!v[n+1]) break; min = oo; for(i = n+1; i != 0; i = link[i]) if(min > map[link[i]][i]) min = map[link[i]][i]; sum += min; for(i = n+1; i != 0; i = link[i]) { map[link[i]][i] -= min;//找超级源点 map[i][link[i]] += min;//找超级汇点 } } return sum; } int main() { int m, flat, cnt, t, k, i, j; while(~scanf("%d %d",&m, &n)) { cnt = 0; for(i = 1; i <= n; i++) { scanf("%d",&f[i].o); for(j = 0; j < m; j++) scanf("%d",&f[i].in[j]); for(j = 0; j < m; j++) scanf("%d",&f[i].out[j]); } memset(map , 0 , sizeof(map));//记录没更新前的值 for(i = 1; i <= n; i++) { int flat1 = 1, flat2 = 1; for(j = 0; j < m; j++) { if(f[i].in[j] == 1) flat1 = 0; if(f[i].out[j] == 0) flat2 = 0; } if(flat1) map[0][i] = f[i].o; if(flat2) map[i][n+1] = f[i].o; for(j = 1; j <= n; j++) { if(i != j) { flat = 1; for(k = 0; k < m; k++) if(f[i].out[k]+f[j].in[k] == 1) { flat = 0; break; } if(flat) map[i][j] = min(f[i].o , f[j].o);//用较小的值当做权值,可以满足到可以留到啊。 } } } memcpy(dp , map , sizeof(map)); t = EK(); for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) if(dp[i][j] > map[i][j]) { s[cnt][0] = i; s[cnt][1] = j; s[cnt++][2] = dp[i][j]-map[i][j];//前后可通过的流量的差就是流过的流量 } printf("%d %d\n",t, cnt); for(i = 0; i < cnt; i++) printf("%d %d %d\n",s[i][0], s[i][1], s[i][2]); } return 0; }