给定n头牛 a种食物 b种饮料
每种食物/饮料只能用一次
一头牛有限定的食物/饮料选择集合
食物饮料均满足则统计个数++ 求最大个数
Solution:
每个牛只配一次 所以拆点
然后就食物连源点 饮料连汇点
牛左右部连边
每个牛左边连食物右边连饮料
上述所有边权均为1
直接最大流完事
(发blog的顺序好像和做的顺序不大一样)
(感觉main压成一行好爽)
Code:
1 #include2 #include 3 #include 4 #include 5 #include 6 #define ms(a,b) memset(a,b,sizeof a) 7 #define rep(i,a,n) for(int i = a;i <= n;i++) 8 #define per(i,n,a) for(int i = n;i >= a;i--) 9 #define inf 214748364710 using namespace std;11 typedef long long ll;12 typedef double D;13 #define eps 1e-814 ll read() {15 ll as = 0,fu = 1;16 char c = getchar();17 while(c < '0' || c > '9') {18 if(c == '-') fu = -1;19 c = getchar();20 }21 while(c >= '0' && c <= '9') {22 as = as * 10 + c - '0';23 c = getchar();24 }25 return as * fu;26 }27 const int N = 10005;28 //head29 int n,A,B;30 int s = N-1,t = N-2;31 int head[N],nxt[N<<1],mo[N<<1],cst[N<<1],cnt = 1;32 void _add(int x,int y,int w) {33 mo[++cnt] = y;34 cst[cnt] = w;35 nxt[cnt] = head[x];36 head[x] = cnt;37 }38 void add(int x,int y) { if(x^y) _add(x,y,1),_add(y,x,0);}39 40 int dep[N],cur[N];41 bool bfs() {42 queue q;43 memcpy(cur,head,sizeof cur);44 ms(dep,0),q.push(s),dep[s] = 1;45 while(!q.empty()) {46 int x = q.front();47 q.pop();48 for(int i = head[x];i;i = nxt[i]) {49 int sn = mo[i];50 if(!dep[sn] && cst[i]) {51 dep[sn] = dep[x] + 1;52 q.push(sn);53 }54 }55 }56 return dep[t];57 }58 59 int dfs(int x,int flow) {60 if(x == t || flow == 0) return flow;61 int res = 0;62 for(int &i = cur[x];i;i = nxt[i]) {63 int sn = mo[i];64 if(dep[sn] == dep[x] + 1 && cst[i]) {65 int d = dfs(sn,min(cst[i],flow - res));66 if(d) {67 cst[i] -= d,cst[i^1] += d;68 res += d;69 if(res == flow) break;70 }71 }72 }73 if(res ^ flow) dep[x] = 0;74 return res;75 }76 77 int DINIC() {78 int ans = 0;79 while(bfs()) ans += dfs(s,inf);80 return ans;81 }82 83 int idx(int x,int f) { return x + f * 1005;}84 85 void init() {86 n = read(),A = read(),B = read();87 rep(i,1,n) {88 int X = read(),Y = read();89 rep(j,1,X) add(idx(read(),0),idx(i,1));90 rep(j,1,Y) add(idx(i,2),idx(read(),3));91 add(idx(i,1),idx(i,2));92 }93 rep(i,1,A) add(s,idx(i,0));94 rep(i,1,B) add(idx(i,3),t);95 }96 97 int main() {init(),printf("%d\n",DINIC());}