某岛

… : "…アッカリ~ン . .. . " .. .
August 16, 2010

ZOJ 2760. How Many Shortest Path

Brief description :

求从源点到终点,互不相交的最短路径的最大值。

Analyse :

预处理完以后,用最大流求边连通度。

/*
    Author: xiaodao
    Prog: ZOJ 2760. How Many Shortest Path
    Status: Accepted
    Last modify: GMT +8 Aug.20th 11:32    
    TAGS: Network-Flow, Floyd
*/

#include 
#include 
#include 
using namespace std;
const int INF = 0x7f7f7f7f;
const int N = 100;
int G[N][N]; bool C[N][N]; int D[N][N];
int P[N], Q[N]; int head, tail;
int n, s, t, u, v;
int ans;



void add_path(){
    ans++;
    while (u!=-2){
        C[u][v] = false; C[v][u] = true;
        v = u; u = P[u];
    }
}

bool find_path(){
    memset(P, -1, sizeof(P));
    Q[0] = s; P[s] = -2; head = 0; tail = 1;
    while (head
/*
    Author: xiaodao
    Prog: ZOJ 2760. How Many Shortest Path
    Status: Accepted
    Last modify: GMT +8 Aug.20th 11:56    
    TAGS: Network-Flow, Dijikstra
*/

#include 
#include 
#include 
using namespace std;
const int INF = 0x7f7f7f7f;
const int N = 100;
int G[N][N]; bool C[N][N]; int D[N];
int P[N], Q[N]; int head, tail; bool V[N];
int n, s, t, u, v;
int ans;



void add_path(){
    ans++;
    while (u!=-2){
        C[u][v] = false; C[v][u] = true;
        v = u; u = P[u];
    }
}

bool find_path(){
    memset(P, -1, sizeof(P));
    Q[0] = s; P[s] = -2; head = 0; tail = 1;
    while (head

...