Brief description :

寻找哪些边的删除会影响最大流流量。

Analyse :

（我之前想的方法一直是扫描每一条边是否饱和。。不过这个想法太暴力了。。因为会存在可以从其他地方绕过这条边而产生同样效果的路径。）

。。。Dinic 完以后，用 Floyd 求残量网络的传递闭包。
注意判断边的时候要两个方向同时呀。

/*
    ID: xiaodao
    PROG: RQ 306. 破坏石油运输系统问题
    TAGS: Network-Flow
*/

#include 
#include 
#include 
using namespace std;
const int INF = 1000000;
const int N = 131, M = N*(N-1)/2;
struct edge{
    int x, y;
};
struct rec{
    int v, p, k;
}; // Stack type
int C[N][N]; // Residual graph ..
int L[N]; edge E[M]; // Leval label ... Edge content.
int n, m, s, t;





void bfs(){
    memset(L, -1, sizeof(L));

    int Q[N], head, tail;

    head = 0; tail = 1; Q[0]  = 1;
    L[1] = 0;

    int u, v;
    while (headn){
                L[u] = -1;
                top--;
            }
            else{
                cache[u] = v+1; top++;
                stack[top].v = v;
                if (C[u][v]  < stack[top-1].k){
                    stack[top].k = C[u][v];
                    stack[top].p = top-1;
                }
                else{
                    stack[top].k = stack[top-1].k;
                    stack[top].p = stack[top-1].p;
                }
            }
        }
        bfs();
    }
}

void solve(){
    bool G[n+1][n+1];

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            G[i][j] = (C[i][j] != 0);

    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                G[i][j] = G[i][j] || (G[i][k] && G[k][j]);

    vector list;
    for (int i=1;i<=m;i++)
        if (!G[E[i].x][E[i].y] || !G[E[i].y][E[i].x]) list.push_back(i);

    cout << list.size() << endl;
    for (int i=0;i> n >> m >> s >> t;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &E[i].x, &E[i].y, &c);
        r(E[i].x); r(E[i].y);
        C[E[i].x][E[i].y] += c;
        C[E[i].y][E[i].x] += c;
    }
}



int main(){
    init(); dinic();
    solve();
}

Posted by xiaodao
Category: 日常