您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

UVA 10480 Sabotage

卞振伟2019-09-25【ACM||算法】人已围观

简介题意:
现在有n个城市,m条路,现在要把整个图分成2部分,编号1,2的城市分成在一部分中,拆开每条路都需要花费,
现在问达成目标的花费最少要隔开那几条路。
题解:
无向图最大流
最小割 == 最大流
bfs k次后,城市1到城市2无增广路,此时城市1相关的城市有分层dis,城市2相关的城市被分割无分层dis
遍历存在边的情况如a、b之间有边,然而a、b有且只有一个有分层dis,则为割边,输出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 100100;
const int maxm = 300000;

struct node {
    int v, w, ne;
} ed[maxm];
int n, m, cnt;
int head[maxn], dis[maxn], cur[maxn];
void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}
void add(int u, int v, int w) { //加边
    ed[cnt].v = v;
    ed[cnt].w = w;
    ed[cnt].ne = head[u];
    head[u] = cnt++;
    ed[cnt].v = u;
    ed[cnt].w = w;
    ed[cnt].ne = head[v];
    head[v] = cnt++;
}
int bfs(int sp, int tp) { //建分层图
    queue<int>q;
    memset(dis, 0, sizeof(dis));
    dis[sp] = 1;
    q.push(sp);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == tp)return 1;
        for (int s = head[u]; ~s; s = ed[s].ne) {
            int v = ed[s].v;
            if (dis[v] == 0 && ed[s].w > 0) {
                if (dis[v] == 0 && ed[s].w > 0) {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }
    }
    return dis[tp] != 0;
}
int dfs(int sp, int tp, int flow) { //寻找增广路
    int ret = flow, a;
    if (sp == tp || flow == 0)return flow;
    for (int &s = cur[sp]; ~s; s = ed[s].ne) {
        int v = ed[s].v;
        if (dis[v] == dis[sp] + 1 && (a = dfs(v, tp, min(ret, ed[s].w)))) {
            ed[s].w -= a;
            ed[s ^ 1].w += a;
            ret -= a;
            if (!ret)break;
        }
    }
    if (ret == flow)dis[sp] = 0;
    return flow - ret;
}
int dinic(int sp, int tp) {
    int ans = 0;
    while (bfs(sp, tp)) {
        for (int s = 0; s <= n; s++)// 遍历  任意点至任到任意点优化
            cur[s] = head[s];
        ans += dfs(sp, tp, inf);
    }
    return ans;
}

int a[maxn], b[maxn];

int main() {
    int t;
    int sp = 0, tp = 0;
    while(~scanf("%d%d", &n, &m)) {
        if(!n && !m)
            break;
        init();
        int x, y, z;
        for(int i = 1; i <= m; ++i){
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
            a[i] = x;
            b[i] = y;
        }
        int ans = dinic(1, 2);
        for(int i = 1; i <= m; ++i){
            if( (!dis[ a[i] ] && dis[ b[i] ] ) || (dis[ a[i] ] && !dis[ b[i] ] )  ){
                printf("%d %d\n", a[i], b[i]);
            }
        }
        printf("\n")
    }
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:HDU 4289 Control

下一篇:HDU 2732 Leapin' Lizards

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:242篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00