scl_网络流.cc

网络流算法的程序以及用网络流解决两个最小割模型的代码

Dinic: 连续最短增广路算法，即一次标号多次增广 O(n^2*m)
#include <algorithm>
using namespace std;

#define MAXN 1010
#define MAXM 2 * MAXN * MAXN
#define INF 0x3fffffff

int N, src, dst;
int n, m;
int c[MAXM], f[MAXM], ev[MAXM], be[MAXM], next[MAXM], num;
int nbs[MAXN], g[MAXN], open[MAXN], d[MAXN], mk[MAXN];

void addEdge(int u, int v, int cc){
    next[++num] = nbs[u]; nbs[u] = num; be[num] = num + 1;
    ev[num] = v; c[num] = cc; f[num] = 0;
    next[++num] = nbs[v]; nbs[v] = num; be[num] = num - 1;
    ev[num] = u; c[num] = 0; f[num] = 0;
}

bool build(int s = src, int t = dst){
    int cur, tail, i, j, u, v;
    memset(d, 0xff, sizeof(d)); memset(g, 0, sizeof(g));
    open[0] = s; d[s] = 0; g[s] = nbs[s];
    for (cur = tail = 0; cur <= tail && d[t] == -1; cur++)
        for (u = open[cur], j = nbs[u]; j; j = next[j]){
            v = ev[j];
            if (d[v] == -1 && f[j] < c[j]){
                open[++tail] = v; 
                d[v] = d[u] + 1; 
                g[v] = nbs[v]; 
            }
        }
    return (d[t] > 0);    
}

int augment(int x = src, int low = INF, int t = dst){
    if (x == t) return low;
    int ret = 0, v;
    for (int &i = g[x]; i; i = next[i]){
        v = ev[i]; 
        if ((c[i] > f[i]) && (d[v] == d[x] + 1)){
            ret = augment(v, low <? c[i] - f[i]);
            if(ret){
                f[i] += ret; f[be[i]] -= ret;
                return ret;
            }
        } 
    }
    return 0;
}

int maxFlow(){
    int flow, ret = 0;
    src = 1; dst = n;
    while (build()) while (flow = augment(src)) ret += flow;
    return ret;
}

int main(){
    int u, v, w;
    while (scanf("%d %d", &m, &n) != EOF){
        num = 0; memset(nbs, 0, sizeof(nbs));
        for (int i = 0; i < m; i++){
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
        }
        printf("%d\n", maxFlow());
    }
    return 0;
}


网络流求最大权闭合图(闭包) 
poj2987

#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 5010;
const __int64 MAXM = 10000000;
const __int64 INF = MAXM * MAXM;

int N, src, dst;
int n, m;
__int64 total;
bool bad;
__int64 c[MAXM], f[MAXM];
int ev[MAXM], be[MAXM], next[MAXM], num;
int nbs[MAXN], g[MAXN], open[MAXN], d[MAXN], mk[MAXN];
//dinic
void addEdge(int u, int v, __int64 cc){
    next[++num] = nbs[u]; nbs[u] = num; be[num] = num + 1;
    ev[num] = v; c[num] = cc; f[num] = 0;
    next[++num] = nbs[v]; nbs[v] = num; be[num] = num - 1;
    ev[num] = u; c[num] = 0; f[num] = 0;
}

bool build(int s = src, int t = dst){
    int cur, tail, i, j, u, v;
    memset(d, 0xff, sizeof(d)); memset(g, 0, sizeof(g));
    open[0] = s; d[s] = 0; g[s] = nbs[s];
    for (cur = tail = 0; cur <= tail && d[t] == -1; cur++)
        for (u = open[cur], j = nbs[u]; j; j = next[j]){
            v = ev[j];
            if (d[v] == -1 && f[j] < c[j]){
                open[++tail] = v; 
                d[v] = d[u] + 1; 
                g[v] = nbs[v]; 
            }
        }
    return (d[t] > 0);    
}

__int64 augment(int x = src, __int64 low = INF, int t = dst){
    if (x == t) return low;
    int ret = 0, v;
    for (int &i = g[x]; i; i = next[i]){
        v = ev[i]; 
        if ((c[i] > f[i]) && (d[v] == d[x] + 1)){
            ret = augment(v, low <? c[i] - f[i]);
            if(ret){
                f[i] += ret; f[be[i]] -= ret;
                return ret;
            }
        } 
    }
    return 0;
}

__int64 maxFlow(){
    __int64 flow, ret = 0;
    while (build()) while (flow = augment(src)) ret += flow;
    return ret;
}
//end of dinic
//build network
bool init(){
    if (scanf("%d %d", &n, &m) == EOF) return false;
    bad = true;
    total = 0; src = 0; dst = n + 1;
    num = 0; memset(nbs, 0, sizeof(nbs));
    __int64 t;
    for (int i = 1; i <= n; i++)
    {
        scanf("%I64d", &t);
        if (t > 0) { bad = false; addEdge(src, i, t); total += t; }
        else if (t < 0) addEdge(i, dst, -t);
    }
    int a, b;
    while (m--){
        scanf("%d %d", &a, &b);
        addEdge(a, b, INF);
    }
    return true;
}
//end of build network
int points;

void dfsvis(int cur) {
    mk[cur] = 1; points++;
    for (int i = nbs[cur]; i; i = next[i])
        if (f[i] < c[i] && !mk[ev[i]]) dfsvis(ev[i]);
}

void solve() {
    if (bad) { printf("0 0\n");  return;}
    __int64 ans = total - maxFlow();
    memset(mk, 0, sizeof(mk));
    points = 0;
    dfsvis(src);
    printf("%d %I64d\n", points - 1, ans);
}

int main(){
    while (init()) solve();
    return 0;
}


最大密度子图 01分数规划+网络流
poj3155
#include <algorithm>
using namespace std;

const int MAXN = 110;
const int MAXM = 1010;

struct Edge{
    int u, v;
    Edge(int u = 0, int v = 0):u(u), v(v){};
};

int n, m;
int deg[MAXN];
Edge e[MAXM];
const double INF = 1e20;
int N, src, dst;
double c[MAXN][MAXN], f[MAXN][MAXN], d[MAXN]; 
int pnt[MAXN], open[MAXN], mk[MAXN];

void init(){
    scanf("%d %d", &n, &m);	
	src = 0; dst = n + 1; N = n + 2;
	int u, v;
    memset(deg, 0, sizeof(deg));
    for (int i = 1; i <= m; i++){
        scanf("%d %d", &u, &v);
        e[i] = Edge(u, v);
        deg[u]++; deg[v]++;
    }
}
//SAP
double maxFlow(int n = N, int s = src, int t = dst)
{
	int cur, tail, u, v; double flow=0;  memset(f,0,sizeof(f));
	do{ memset(mk,0,sizeof(mk)); memset(d,0,sizeof(d));
		open[0]=s; mk[s]=1; d[s]=INF;
		for(pnt[s]=cur=tail=0;cur<=tail&&!mk[t];cur++)
			for(u=open[cur],v=0;v<n;v++)if(!mk[v]&&f[u][v]<c[u][v]){
				mk[v]=1; open[++tail]=v; pnt[v]=u;
				if(d[u]<c[u][v]-f[u][v])d[v]=d[u];
					else d[v]=c[u][v]-f[u][v];
			}
		if(!mk[t])break; flow+=d[t];
		for(u=t;u!=s;){v=u;u=pnt[v];f[u][v]+=d[t]; f[v][u]=-f[u][v];}
	}while(d[t]>0); return flow;
}

int ans;
void dfsvis(int u){
	mk[u]=1; ans++;
	for(int v = 0; v < N; ++v) if( dcmp(f[u][v]-c[u][v]) < 0 && !mk[v] )
		dfsvis(v);
}

double h(double g){
	memset(c, 0, sizeof(c));
    for (int i = 1; i <= m; i++) {c[e[i]. u][e[i]. v] = 1.0; c[e[i]. v][e[i]. u] = 1.0;}
    for (int i = 1; i <= n; i++) {c[src][i] = m; c[i][dst] = m + 2*g - deg[i];}
    double f = maxFlow();
    return 1.0*m*n - f;
}

void solve(){
	if (m == 0){ puts("1\n1"); return;};
    double low = 0.0, high = m, mid;
    while (low + 1.0/n/n< high){
        mid = (low + high) / 2;
        if (h(mid) <= 0) high = mid; else low = mid;
    }
    h(low);
    ans = 0; memset(mk, 0, sizeof(mk));
    dfsvis(src);
    printf("%d\n", ans - 1);        
    for (int i = 1; i <= n; i++) 
        if (mk[i]) printf("%d\n", i);
}

int main(){
    init();
    solve();
    return 0;
}