做的好的购物网站,框架网站模板,西安最好的室内设计公司,中国建设会计协会网站题目链接 简介#xff1a;交换贴纸 分析#xff1a; 这也算是一个天坑了 很久之前就看过这道题#xff0c;但是一直没有填 美妙的建图#xff1a; 我们用n-1个点表示每个除Bob之外的人 用m个点表示贴纸#xff0c;从源点向这m个点连边#xff0c;边的容量是Bob拥有该… 题目链接 简介交换贴纸 分析 这也算是一个天坑了 很久之前就看过这道题但是一直没有填 美妙的建图 我们用n-1个点表示每个除Bob之外的人 用m个点表示贴纸从源点向这m个点连边边的容量是Bob拥有该种贴纸的数量 接下来我们要连接其他人和贴纸 如果第i个人有超过一张j种贴纸有k张那么我们就连接i—j容量为k-1表示ta可以贡献出k-1张第j种贴纸 如果第i个人没有第j种贴纸那么我们连接j—i容量为1表示ta最多接受一张j贴纸 最后所有的贴纸连向汇点流量为1 最大流即为最后答案 附样例图 //这里写代码片
#includecstdio
#includecstring
#includeiostream
#includequeueusing namespace std;const int N101;
const int INF0x33333333;
struct node{int x,y,v,nxt;
};
node way[N*N];
int st[N],tot,deep[N],cur[N],s,t;
int n,m,zl[30][30];void add(int u,int w,int z)
{tot;way[tot].xu;way[tot].yw;way[tot].vz;way[tot].nxtst[u];st[u]tot;tot;way[tot].xw;way[tot].yu;way[tot].v0;way[tot].nxtst[w];st[w]tot;
}int bfs(int s,int t)
{for (int is;it;i) cur[i]st[i];memset(deep,-1,sizeof(deep));queueint Q;Q.push(s);deep[s]1;while (!Q.empty()){int nowQ.front(); Q.pop();for (int ist[now];i!-1;iway[i].nxt)if (way[i].vdeep[way[i].y]-1){deep[way[i].y]deep[now]1;Q.push(way[i].y);}}return deep[t]!-1;
}int dfs(int now,int t,int limit)
{if (nowt||!limit) return limit;int f,flow0;for (int icur[now];i!-1;iway[i].nxt){cur[now]i;if (way[i].vdeep[way[i].y]deep[now]1(fdfs(way[i].y,t,min(limit,way[i].v)))){flowf;limit-f;way[i].v-f;way[i^1].vf;if (!limit) break;}}return flow;
}int dinic()
{int ans0;while (bfs(s,t))ansdfs(s,t,INF);return ans;
}int main()
{int T;scanf(%d,T);for (int cas1;casT;cas){memset(st,-1,sizeof(st));tot-1;scanf(%d%d,n,m);memset(zl,0,sizeof(zl));for (int i1;in;i){ int k,x; //inputscanf(%d,k);for (int l1;lk;l)scanf(%d,x),zl[i][x];}s0; tnm1;for (int i1;im;i){if (zl[1][i]) add(s,i,zl[1][i]);add(i,t,1);} for (int i2;in;i)for (int j1;jm;j){if (zl[i][j]1) //可以给出一张j add(im,j,zl[i][j]-1);if (!zl[i][j]) //没有j最多可以接受一张j add(j,im,1);}printf(Case #%d: %d\n,cas,dinic());} return 0;
}转载于:https://www.cnblogs.com/wutongtong3117/p/7673029.html