首页 > 代码库 > A simple brute force problem.
A simple brute force problem.
hdu4971:http://acm.hdu.edu.cn/showproblem.php?pid=4971
题意：给你n个项目，每完成一个项目会有一定的收益，但是为了完成某个项目，要先学会一些技能，学习每个技能会有一定的花费。并且，在学习某项技能之前，可能需要需要先学习前一种技能，最后问你最后能够获得的最大的收益。
题解:这一题，很容易想到网络流，关键是建图，首先把每个技能拆点，两个点之间的容量就是每个技能的花费。人然后右边的边和会点建立一边，容量无穷大,然后就是每个项目的到技能左边的点连接一条边，容量无穷大，然后是源点和每个项目之间建立一条边，容量就是收益。最后就是技能之间的，如果学习i技能之前要学习j技能，那么i的左端点到j的左端点之间连一边，容量无穷大。然后跑网络流，最终的答案就是总收益减去总流量。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<queue> 6 #define INF 100000000 7 using namespace std; 8 const int N=205; 9 const int M=1000000; 10 struct Node{ 11 int v; 12 int f; 13 int next; 14 }edge[M]; 15 int n,m,u,v,cnt,sx,ex; 16 int head[N],pre[N],visit[N]; 17 int val1[N],val2[N]; 18 void init(){ 19 cnt=0; 20 //memset(edge,0,sizeof(edge)); 21 memset(head,-1,sizeof(head)); 22 } 23 void add(int u,int v,int w){ 24 edge[cnt].v=v; 25 edge[cnt].f=w; 26 edge[cnt].next=head[u]; 27 head[u]=cnt++; 28 edge[cnt].f=0; 29 edge[cnt].v=u; 30 edge[cnt].next=head[v]; 31 head[v]=cnt++; 32 } 33 bool BFS(){ 34 memset(pre,0,sizeof(pre)); 35 pre[sx]=1; 36 queue<int>Q; 37 Q.push(sx); 38 while(!Q.empty()){ 39 int d=Q.front(); 40 Q.pop(); 41 for(int i=head[d];i!=-1;i=edge[i].next ){ 42 if(edge[i].f&&!pre[edge[i].v]){ 43 pre[edge[i].v]=pre[d]+1; 44 Q.push(edge[i].v); 45 } 46 } 47 } 48 return pre[ex]>0; 49 } 50 int dinic(int flow,int ps){ 51 int f=flow; 52 if(ps==ex)return f; 53 for(int i=head[ps];i!=-1;i=edge[i].next){ 54 if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){ 55 int a=edge[i].f; 56 int t=dinic(min(a,flow),edge[i].v); 57 edge[i].f-=t; 58 edge[i^1].f+=t; 59 flow-=t; 60 if(flow<=0)break; 61 } 62 63 } 64 if(f-flow<=0)pre[ps]=-1; 65 return f-flow; 66 } 67 int solve(){ 68 int sum=0; 69 while(BFS()) 70 sum+=dinic(INF,sx); 71 return sum; 72 } 73 int main() { 74 int T,k,temp,sum,tt=1; 75 scanf("%d",&T); 76 while(T--) { 77 scanf("%d%d",&n,&m); 78 sum=0; 79 init(); 80 for(int i=1; i<=n; i++) { 81 scanf("%d",&val1[i]); 82 sum+=val1[i]; 83 } 84 for(int j=1;j<=m;j++) 85 scanf("%d",&val2[j]); 86 for(int i=1;i<=n;i++){ 87 scanf("%d",&k); 88 for(int j=1;j<=k;j++){ 89 scanf("%d",&temp); 90 add(2*m+i,temp+1,INF); 91 } 92 add(0,2*m+i,val1[i]); 93 } 94 for(int i=1;i<=m;i++){ 95 for(int j=1;j<=m;j++){ 96 scanf("%d",&temp); 97 if(temp==1){ 98 add(i,j,INF); 99 }100 }101 }102 for(int i=1;i<=m;i++){103 add(i,i+m,val2[i]);104 add(i+m,2*m+n+1,INF);105 }106 sx=0;ex=2*m+n+1;107 printf("Case #%d: %d\n",tt++,sum-solve());108 }109 return 0;110 }
A simple brute force problem.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。