Base Station

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

4

把边当做点，当选择一条边时候，必然要选择它所连接的两个顶点，这样就转化成最大权闭合子图模型，

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/3/9 22:00:26
File Name :A.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
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]<N){
        if(u==t){
            int temp=INF,id;
            for( i=0;i<top;i++)
               if(temp>edge[S[i]].cap)
                   temp=edge[S[i]].cap,id=i;
            for( i=0;i<top;i++)
                  edge[S[i]].cap-=temp,edge[S[i]^1].cap+=temp;
            res+=temp;top=id;u=edge[S[top]^1].to;
        }
        if(u!=t&&gap[dep[u]-1]==0)break;
        for( i=cur[u];i!=-1;i=edge[i].next)
            if(edge[i].cap&&dep[u]==dep[edge[i].to]+1)break;
        if(i!=-1)cur[u]=i,S[top++]=i,u=edge[i].to;
        else{
            int MIN=N;
            for( i=head[u];i!=-1;i=edge[i].next)
                if(edge[i].cap&&MIN>dep[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<<sum-sap(0,m+n+1,10*n+m+1)<<endl;

     }
     return 0;
}

hdu 3879 最大权闭合子图,布布扣,bubuko.com

hdu 3879 最大权闭合子图

原文：http://blog.csdn.net/xianxingwuguan1/article/details/20911441