首页 > 代码库 > POJ 3469 Dual Core CPU
POJ 3469 Dual Core CPU
Dual Core CPU
Time Limit: 15000ms
Memory Limit: 131072KB
This problem will be judged on PKU. Original ID: 346964-bit integer IO format: %lld Java class name: Main
As more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.
The routine consists of N modules, and each of them should run in a certain core. The costs for all the routines to execute on two cores has been estimated. Let‘s define them as Ai and Bi. Meanwhile, M pairs of modules need to do some data-exchange. If they are running on the same core, then the cost of this action can be ignored. Otherwise, some extra cost are needed. You should arrange wisely to minimize the total cost.
Input
There are two integers in the first line of input data, N and M (1 ≤ N ≤ 20000, 1 ≤ M ≤ 200000) .The next N lines, each contains two integer, Aiand Bi.In the following M lines, each contains three integers: a, b, w. The meaning is that if module a and module b don‘t execute on the same core, you should pay extra w dollars for the data-exchange between them.
Output
Output only one integer, the minimum total cost.
Sample Input
3 11 102 1010 32 3 1000
Sample Output
13
Source
POJ Monthly--2007.11.25
解题：比较经典的最小割模型。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 20100;18 struct arc{19 int to,flow,next;20 arc(int x = 0,int y = 0,int z = -1){21 to = x;22 flow = y;23 next = z;24 }25 };26 arc e[1000000];27 int head[maxn],d[maxn],cur[maxn],tot,S,T;28 int q[maxn<<2],hd,tl;29 void add(int u,int v,int w){30 e[tot] = arc(v,w,head[u]);31 head[u] = tot++;32 e[tot] = arc(u,0,head[v]);33 head[v] = tot++;34 }35 bool bfs(){36 memset(d,-1,sizeof(d));37 hd = tl = 0;38 q[tl++] = S;39 d[S] = 1;40 while(hd < tl){41 int u = q[hd++];42 for(int i = head[u]; ~i; i = e[i].next){43 if(e[i].flow && d[e[i].to] == -1){44 d[e[i].to] = d[u] + 1;45 q[tl++] = e[i].to;46 }47 }48 }49 return d[T] > -1;50 }51 int dfs(int u,int low){52 if(u == T) return low;53 int tmp = 0,a;54 for(int &i = cur[u]; ~i; i = e[i].next){55 if(e[i].flow && d[e[i].to] == d[u] + 1 && (a = dfs(e[i].to,min(e[i].flow,low)))){56 tmp += a;57 low -= a;58 e[i].flow -= a;59 e[i^1].flow += a;60 if(!low) break;61 }62 }63 if(!tmp) d[u] = -1;64 return tmp;65 }66 int main() {67 int u,v,w,ans,n,m;68 while(~scanf("%d %d",&n,&m)){69 memset(head,-1,sizeof(head));70 ans = S = tot = 0;71 T = n + 1;72 for(int i = 1; i <= n; i++){73 scanf("%d %d",&u,&v);74 add(S,i,u);75 add(i,T,v);76 }77 for(int i = 0; i < m; i++){78 scanf("%d %d %d",&u,&v,&w);79 add(u,v,w);80 add(v,u,w);81 }82 while(bfs()){83 memcpy(cur,head,sizeof(head));84 ans += dfs(S,INF);85 }86 printf("%d\n",ans);87 }88 return 0;89 }
加输入挂的ISAP在g++下表现不错
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 20100; 18 struct arc { 19 int to,flow,next; 20 arc(int x = 0,int y = 0,int z = -1) { 21 to = x; 22 flow = y; 23 next = z; 24 } 25 }; 26 arc e[1000000]; 27 int head[maxn],gap[maxn],d[maxn],cur[maxn]; 28 int S,T,tot,hd,tl,q[maxn],p[maxn]; 29 int getnum() { 30 char ch; 31 int num = 0,flag = 0; 32 while(((ch = getchar()) < ‘0‘ || ch > ‘9‘) && ch != ‘-‘) 33 if(ch == EOF) exit(0); 34 if(ch == ‘-‘) flag = 1; 35 else num = ch - ‘0‘; 36 while((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) 37 num = num * 10 + ch - ‘0‘; 38 if(flag) num *= -1; 39 return num; 40 } 41 void add(int u,int v,int w) { 42 e[tot] = arc(v,w,head[u]); 43 head[u] = tot++; 44 e[tot] = arc(u,0,head[v]); 45 head[v] = tot++; 46 } 47 void bfs() { 48 hd = tl = 0; 49 memset(d,-1,sizeof(d)); 50 memset(gap,0,sizeof(gap)); 51 q[tl++] = T; 52 d[T] = 0; 53 while(hd < tl) { 54 int u = q[hd++]; 55 ++gap[d[u]]; 56 for(int i = head[u]; ~i; i = e[i].next) { 57 if(d[e[i].to] == -1) { 58 d[e[i].to] = d[u] + 1; 59 q[tl++] = e[i].to; 60 } 61 } 62 } 63 } 64 int isap() { 65 int maxFlow = 0,flow = INF,u = S; 66 memcpy(cur,head,sizeof(head)); 67 bfs(); 68 while(d[S] < T) { 69 int &i = cur[u]; 70 for(; ~i; i = e[i].next) 71 if(e[i].flow && d[e[i].to] + 1 == d[u]) break; 72 if(i > -1) { 73 flow = min(flow,e[i].flow); 74 p[u = e[i].to] = i; 75 if(u == T) { 76 do { 77 int v = p[u]; 78 e[v].flow -= flow; 79 e[v^1].flow += flow; 80 u = e[v^1].to; 81 } while(u != S); 82 maxFlow += flow; 83 flow = INF; 84 } 85 } else { 86 if(--gap[d[u]] == 0) break; 87 d[u] = T; 88 cur[u] = head[u]; 89 for(int k = head[u]; ~k; k = e[k].next) 90 if(e[k].flow && d[e[k].to] + 1 < d[u]) 91 d[u] = d[e[k].to] + 1; 92 ++gap[d[u]]; 93 if(u != S) u = e[p[u]^1].to; 94 } 95 } 96 return maxFlow; 97 } 98 int main() { 99 int n,m,u,v,w;100 while(~scanf("%d %d",&n,&m)) {101 memset(head,-1,sizeof(head));102 S = tot = 0;103 T = n + 1;104 for(int i = 1; i <= n; i++) {105 //scanf("%d %d",&u,&v);106 u = getnum();107 v = getnum();108 add(S,i,u);109 add(i,T,v);110 }111 for(int i = 0; i < m; i++) {112 //scanf("%d %d %d",&u,&v,&w);113 u = getnum();114 v = getnum();115 w = getnum();116 add(u,v,w);117 add(v,u,w);118 }119 printf("%d\n",isap());120 }121 return 0;122 }
POJ 3469 Dual Core CPU
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。