程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3469 最小割

POJ 3469 最小割

編輯：C++入門知識

Dual Core CPU Time Limit: 15000MS Memory Limit: 131072K Total Submissions: 17675 Accepted: 7631 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 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 A_i and B_i. 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, A_i and B_i.
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

Sample Output

題意：給定n個部件，在A，B兩個內核上運行的費用給定，假如某兩個部件不在同一個內核上運行，需要額外支付一定錢，求最小花費，

對於每一個部件，從源點向其連邊，流量為在a上運行的費用，從其向匯點連邊流量為在b上運行的時間，給定的關系的加雙向邊，

根據最小割最大流定理，最小割等於最大流，求出來等於答案。

代碼：

/* ***********************************************
Author :rabbit
Created Time :2014/3/8 22:19:12
File Name :treap2.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 10000000000000LL
#define eps 1e-8
#define pi acos(-1.0)
typedef int ll;
const ll maxn=31909;
const ll maxm=4000010;
struct Edge{
    ll to,next,cap,flow;
    Edge(){};
    Edge(ll _next,ll _to,ll _cap,ll _flow){
        next=_next;to=_to;cap=_cap;flow=_flow;
    }
}edge[maxm];
ll head[maxn],tol,gap[maxn],dep[maxn],cur[maxn];
void addedge(ll u,ll v,ll flow){
    edge[tol]=Edge(head[u],v,flow,0);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0,0);head[v]=tol++;
}
ll Q[maxn];
void bfs(ll start,ll end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]++;ll front=0,rear=0;
    dep[end]=0;Q[rear++]=end;
    while(front!=rear){
        ll u=Q[front++];
        for(ll i=head[u];i!=-1;i=edge[i].next){
            ll v=edge[i].to;if(dep[v]==-1&&edge[i].cap)
                Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
}
ll S[maxn];
ll sap(ll start,ll end,ll N){
    bfs(start,end);
    memcpy(cur,head,sizeof(head));
    ll top=0,u=start,ans=0;
    while(dep[start]edge[S[i]].cap-edge[S[i]].flow)
                    MIN=edge[S[i]].cap-edge[S[i]].flow,id=i;
            for(ll i=0;i