Language:
Dual Core CPU
Time Limit:15000MSMemory Limit:131072K
Total Submissions:19820Accepted:8601
Case Time Limit:5000MS
Description
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 ofNmodules, 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 asAiandBi. Meanwhile,Mpairs 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,NandM(1 ≤N≤ 20000, 1 ≤M≤ 200000) .The nextNlines, each contains two integer,AiandBi.In the followingMlines, each contains three integers:a,b,w. The meaning is that if moduleaand modulebdon’t execute on the same core, you should pay extrawdollars 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
, Zhou Dong
题意：现在有n个模块，两个CPU A和B，每个模块要么在A上运行，要么在B上运行，给出每个模块在A和B机器上运行所需要的费用。接着m行，每行 a，b，w三个数字。表示如果a模块和b模块不在同一个机器上运行的话，需要额外花费w来共享数据。现在要求出运行所有任务最小的花费是多少。
思路：将两个CPU视为源点和汇点，对第i个模块在每个CPU中的耗费Ai和Bi，从源点向顶点i连接一条容量为Ai的弧，从顶点i向汇点连接一条容量为Bi的弧；对于a模块和b模块在不同CPU中运行造成的耗费w，从顶点a向b连容量为w的双向边。求最小割即求最大流。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 1005#define MAXN 20005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FRL(i,a,b) for(i = a; i < b; i++)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")const int MAXM = 480010;typedef long long ll;using namespace std;struct Edge{int to,next,cap,flow;}edge[MAXM];int n,m,s,t;int tol;int head[MAXN];int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];void init(){tol=0;memset(head,-1,sizeof(head));}//加边，单向图三个参数，双向图四个参数void addedge(int u,int v,int w,int rw=0){edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u];edge[tol].flow=0; head[u]=tol++;edge[tol].to=u; edge[tol].cap=rw; edge[tol].next=head[v];edge[tol].flow=0; head[v]=tol++;}//输入参数：起点，终点，，点的总数//点的编号没有影响，只要输入点的总数int sap(int start,int end,int N){memset(gap,0,sizeof(gap));memset(dep,0,sizeof(dep));memcpy(cur,head,sizeof(head));int u=start;pre[u]=-1;gap[0]=N;int ans=0;while (dep[start]<N){if (u==end){int Min=INF;for (int i=pre[u];i!=-1;i=pre[edge[i^1].to])if (Min>edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;for (int i=pre[u];i!=-1;i=pre[edge[i^1].to]){edge[i].flow+=Min;edge[i^1].flow-=Min;}u=start;ans+=Min;continue;}bool flag=false;int v;for (int i=cur[u];i!=-1;i=edge[i].next){v=edge[i].to;if (edge[i].cap-edge[i].flow && dep[v]+1==dep[u]){flag=true;cur[u]=pre[v]=i;break;}}if (flag){u=v;continue;}int Min=N;for (int i=head[u];i!=-1;i=edge[i].next)if (edge[i].cap-edge[i].flow && dep[edge[i].to]<Min){Min=dep[edge[i].to];cur[u]=i;}gap[dep[u]]–;if (!gap[dep[u]]) return ans;dep[u]=Min+1;gap[dep[u]]++;if (u!=start) u=edge[pre[u]^1].to;}return ans;}int main(){int i,j;while (~sff(n,m)){int a,b,c;init();s=0;t=n+1;FRE(i,1,n){sff(a,b);addedge(s,i,a);addedge(i,t,b);}FRE(i,1,m){sfff(a,b,c);addedge(a,b,c,c);}printf("%d\n",sap(s,t,t+1));}return 0;}/*3 11 102 1010 32 3 1000*/
莫愁前路无知己，天下谁人不识君。
