程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> spoj1476 maximum profit,最大權閉合子圖

spoj1476 maximum profit,最大權閉合子圖

編輯：C++入門知識

spoj1476 maximum profit,最大權閉合子圖

最大權閉合子圖：點權之和最大的閉合圖。

建圖：每一條有向邊變為容量為inf，源S到正權點v(wv>0)的邊容量wv，負權點v(wv<0)到匯T的邊容量−wv，零權點v(wv=0)不與源和匯相連。然後求最小割(SUM-最大流)即為答案。

/*
 * Author: yew1eb
 * Created Time:  2014年10月31日 星期五 15時39分22秒
 * File Name: spoj1476 maximum profit.cpp
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll  INF = 1e18;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxn = 60010;
const int maxm = 2000010;

struct Edge {
    int to, cap, next;
    Edge(int _next=0,int _to=0,int _cap=0):next(_next),to(_to),cap(_cap) {}
} edge[maxm];

int n, m, S, T, cnt;
int head[maxn], tot;
int d[maxn];//到匯點的距離下界。
int gap[maxn];

void init()
{
    tot = 0;
    memset(head, -1, sizeof head );
}

void add(int u,int v,int c, int rc=0)
{
    edge[tot] = Edge(head[u], v, c);
    head[u] = tot++;
    edge[tot] = Edge(head[v], u, rc);
    head[v] = tot++;
}


int get_flow(int u, int flow)
{
    if(u==T || flow==0)return flow;
    int res=0, f;
    for(int i=head[u]; ~i; i=edge[i].next) {
        int &v = edge[i].to;
        if(d[u]>d[v] && (f=get_flow(v,min(flow,edge[i].cap)))>0) {
            edge[i].cap -= f;
            edge[i^1].cap += f;
            res += f;
            flow -= f;
            if(flow==0) return res;
        }
    }
    if(!(--gap[d[u]]))d[S]=cnt+2;
    gap[++d[u]]++;
    return res;
}

int isap()
{
    int flow = 0;
    memset(gap, 0, sizeof gap );
    memset(d, 0, sizeof d );
	cnt = T-S+1;
    gap[0] = cnt;
    while(d[S]

C++入門知識

C++編程中的細節--內容覆蓋

一個

POJ 1925 Spiderman

Spiderman Time Limit: 5000M

UVA 10213 How Many Pieces of Land? 歐拉定理

UVA 10213 How Many Pieces of L

揭開Socket編程的面紗(1)

對TCP/IP、UDP、Socket編程這些詞你不會很陌生

poj-3422-Kaka&#39;s Matrix Travels-最小費用最大流

最小費用最大流。建圖方式如圖所示然後就是費用流

poj1328Radar Installation(貪心—區間選點)

poj1328Radar Installation(貪心—區