程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3879 最大權閉合子圖

hdu 3879 最大權閉合子圖

編輯：C++入門知識

Base Station

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65768/32768 K (Java/Others)
Total Submission(s): 1556 Accepted Submission(s): 646

Problem Description A famous mobile communication company is planning to build a new set of base stations. According to the previous investigation, n places are chosen as the possible new locations to build those new stations. However, the condition of each position varies much, so the costs to built a station at different places are different. The cost to build a new station at the ith place is P_i (1<=i<=n).

When complete building, two places which both have stations can communicate with each other.

Besides, according to the marketing department, the company has received m requirements. The ith requirement is represented by three integers A_i, B_i and C_i, which means if place A_iand B_i can communicate with each other, the company will get C_i profit.

Now, the company wants to maximize the profits, so maybe just part of the possible locations will be chosen to build new stations. The boss wants to know the maximum profits.
Input Multiple test cases (no more than 20), for each test case:
The first line has two integers n (0 The second line has n integers, P1 through Pn, describes the cost of each location.
Next m line, each line contains three integers, A_i, B_i and C_i, describes the ith requirement.
Output One integer each case, the maximum profit of the company.
Sample Input

Sample Output

把邊當做點，當選擇一條邊時候，必然要選擇它所連接的兩個頂點，這樣就轉化成最大權閉合子圖模型，

代碼：

/* ***********************************************
Author :rabbit
Created Time :2014/3/9 22:00:26
File Name :A.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 10000000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=60010;
const int maxm=1002000;
struct Edge{
    int next,to,cap;
    Edge(){};
    Edge(int _next,int _to,int _cap){
        next=_next;to=_to;cap=_cap;
    }
}edge[maxm];
int head[maxn],tol,dep[maxn],gap[maxn];
void addedge(int u,int v,int flow){
    edge[tol]=Edge(head[u],v,flow);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0);head[v]=tol++;
}
void bfs(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]++;int front=0,rear=0,Q[maxn];
    dep[end]=0;Q[rear++]=end;
    while(front!=rear){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;if(dep[v]==-1)
                Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
}
int sap(int s,int t,int N){
    int res=0;bfs(s,t);
    int cur[maxn],S[maxn],top=0,u=s,i;
    memcpy(cur,head,sizeof(head));
    while(dep[s]edge[S[i]].cap)
                   temp=edge[S[i]].cap,id=i;
            for( i=0;idep[edge[i].to])
                    MIN=dep[edge[i].to],cur[u]=i;
            --gap[dep[u]];++gap[dep[u]=MIN+1];
            if(u!=s)u=edge[S[--top]^1].to;
        }
    }
    return res;
}
int in[maxn];
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n,m;
     while(~scanf("%d%d",&n,&m)){
         memset(head,-1,sizeof(head));tol=0;
         for(int i=1;i<=n;i++){
             int j;
             scanf("%d",&j);
             addedge(i,m+n+1,j);
         }
         int sum=0;
         for(int i=1;i<=m;i++){
             int a,b,c;
             scanf("%d%d%d",&a,&b,&c);
             addedge(0,i+n,c);
             addedge(i+n,a,INF);
             addedge(i+n,b,INF);
             sum+=c;
         }
         cout<