当前位置:编程学习 > C/C++ >>

ZOJ 2587 最小割的唯一性

题意还行,就是问最小割是不是唯一的。
假设源点为s,汇点为t,最小割将点集分为两个点集S,T
那么S的一种情况就是,从源点出发,dfs残留网络,沿着不满流的边走,能走到的所有点都属于S,全集减去S即为T。
T的一种情况是,如果一个点沿着一些不满流的边能到达汇点,那么该点属于T。
而本题要求的是唯一性,观察网络有这样一个特性,一个点如果既不能由S沿着不满流的边到达,也不能沿着一些不满流的边到达T,那么该点既可以属于S,也可属于T,那么最小割不是唯一的。
为什么呢? 如果一个点v不能由S沿着不满流的边到达,必然是S到v的所有边都满流,同样如果v沿着不满流的边到不了T,v到T的所有边也都是满流,并且,S到v的流量等于v到T的流量,否则两边流量不对等会导致不满流的边出现,此时既然流量相等,那么v属于S或者T都是可以的,也就是说最小割不唯一
这里搜索要搜两次,一次是从源点出发,另一次是从汇点出发搜索逆图

[cpp] 
#include <iostream> 
#include <algorithm> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <cmath> 
#include <queue> 
#include <map> 
#include <set> 
#define eps 1e-5 
#define MAXN 1111 
#define MAXM 55555 
#define INF 10000007 
using namespace std; 
struct node 

    int u, v;    // vtex 
    int c;    // cacity 
    int f;   // current f in this arc 
    int next, r; 
} edge[MAXM]; 
int dist[MAXN], nm[MAXN], src, des, n; 
int head[MAXN], e; 
void add(int x, int y, int c) 

    edge[e].u = x; 
    edge[e].v = y; 
    edge[e].c = c; 
    edge[e].f = 0; 
    edge[e].r = e + 1; 
    edge[e].next = head[x]; 
    head[x] = e++; 
    edge[e].u = y; 
    edge[e].v = x; 
    edge[e].c = 0; 
    edge[e].f = 0; 
    edge[e].r = e - 1; 
    edge[e].next = head[y]; 
    head[y] = e++; 

void rev_BFS() 

    int Q[MAXN], h = 0, t = 0; 
    for(int i = 1; i <= n; ++i) 
    { 
        dist[i] = MAXN; 
        nm[i] = 0; 
    } 
    Q[t++] = des; 
    dist[des] = 0; 
    nm[0] = 1; 
    while(h != t) 
    { 
        int v = Q[h++]; 
        for(int i = head[v]; i != -1; i = edge[i].next) 
        { 
            if(edge[edge[i].r].c == 0 || dist[edge[i].v] < MAXN)continue; 
            dist[edge[i].v] = dist[v] + 1; 
            ++nm[dist[edge[i].v]]; 
            Q[t++] = edge[i].v; 
        } 
    } 

void init() 

    e = 0; 
    memset(head, -1, sizeof(head)); 

int maxflow() 

    rev_BFS(); 
    int u; 
    int total = 0; 
    int cur[MAXN], rpath[MAXN]; 
    for(int i = 1; i <= n; ++i)cur[i] = head[i]; 
    u = src; 
    while(dist[src] < n) 
    { 
        if(u == des)     // find an augmenting path 
        { 
            int tf = INF; 
            for(int i = src; i != des; i = edge[cur[i]].v) 
                tf = min(tf, edge[cur[i]].c); 
            for(int i = src; i != des; i = edge[cur[i]].v) 
            { 
                edge[cur[i]].c -= tf; 
                edge[edge[cur[i]].r].c += tf; 
                edge[cur[i]].f += tf; 
                edge[edge[cur[i]].r].f -= tf; 
            } 
            total += tf; 
            u = src; 
        } 
        int i; 
        for(i = cur[u]; i != -1; i = edge[i].next) 
            if(edge[i].c > 0 && dist[u] == dist[edge[i].v] + 1)break; 
        if(i != -1)     // find an admissible arc, then Advance 
        { 
            cur[u] = i; 
            rpath[edge[i].v] = edge[i].r; 
            u = edge[i].v; 
        } 
        else        // no admissible arc, then relabel this vtex 
        { 
            if(0 == (--nm[dist[u]]))break;    // GAP cut, Important! 
            cur[u] = head[u]; 
            int mindist = n; 
            for(int j = head[u]; j != -1; j = edge[j].next) 
                if(edge[j].c > 0)mindist = min(mindist, dist[edge[j].v]); 
            dist[u] = mindist + 1; 
            ++nm[dist[u]]; 
            if(u != src) 
          

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,