hdu4971 流-最大权闭包

题意：
      给了一些任务，然后给了一些完成某些任务的限制，然后又给了限制之间的拓扑关系，最后问你最大收益。

思路：
      很直白，就是流的一个应用，最大权闭包，没涉及到什么想法的地方，建图也不坑，直接说建图吧，
s - 所有任务  流量是 任务价值
所有限制 - t  流量是 限制代价
a -> b 流量 INF a限制的拓扑关系在b的后面

最后答案是 所有任务的价值 - maxflow

#include<stdio.h> #include<string.h> #include<queue>#define N_node 100 #define N_edge 8000 #define INF 1000000000 using namespace std;typedef struct {int to ,next ,cost; }STAR;typedef struct {int x ,t; }DEP;STAR E[N_edge]; DEP xin ,tou; int list[N_node] ,listt[N_node] ,tot; int deep[N_node];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot;E[++tot].to = a;E[tot].cost = 0;E[tot].next = list[b];list[b] = tot; }bool BFS_Deep(int s ,int t ,int n) {memset(deep ,255 ,sizeof(deep));deep[s] = 0;xin.x = s ,xin.t = 0;queue<DEP>q;q.push(xin);while(!q.empty()){tou = q.front();q.pop();for(int k = list[tou.x] ;k ;k = E[k].next){xin.x = E[k].to;xin.t = tou.t + 1;if(deep[xin.x] != -1 || !E[k].cost)continue;deep[xin.x] = xin.t;q.push(xin);}}for(int i = 0 ;i <= n ;i ++)listt[i] = list[i];return deep[t] != -1; }int minn(int x ,int y) {return x < y ? x : y; }int DFS_Flow(int s ,int t ,int flow) {if(s == t) return flow;int nowflow = 0;for(int k = listt[s] ;k ;k = E[k].next){listt[s] = k;int to = E[k].to;int c = E[k].cost;if(deep[to] != deep[s] + 1 || !c)continue;int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));nowflow += tmp;E[k].cost -= tmp;E[k^1].cost += tmp;if(nowflow == flow) break;}if(!nowflow) deep[s] = 0;return nowflow; }int DINIC(int s ,int t ,int n) {int ans = 0;while(BFS_Deep(s ,t ,n)){ans += DFS_Flow(s ,t ,INF);}return ans; }int main () {int i ,j ,n ,nn ,m ,a ,T ,cas = 1;int s ,t ,sum_z;scanf("%d" ,&T);while(T--){scanf("%d %d" ,&n ,&m);s = 0 ,t = n + m + 1;memset(list ,0 ,sizeof(list)) ,tot = 1;for(sum_z = 0 ,i = 1 ;i <= n ;i ++){scanf("%d" ,&a);sum_z += a;add(s ,i ,a);}for(i = 1 ;i <= m ;i ++){scanf("%d" ,&a);add(i + n ,t ,a);}for(i = 1 ;i <= n ;i ++){scanf("%d" ,&nn);while(nn--){scanf("%d" ,&a);a ++;add(i ,a + n ,INF);}}for(i = 1 ;i <= m ;i ++)for(j = 1 ;j <= m ;j ++){scanf("%d" ,&a);if(a) add(i + n ,j + n ,INF);}printf("Case #%d: " ,cas ++);printf("%d\n" ,sum_z - DINIC(s ,t ,t));}return 0; }

总结

以上是生活随笔为你收集整理的hdu4971 流-最大权闭包的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。