无知 无求

0%

uva10480 Sabotage

发表于 更新于 分类于 ，

n个城市m条边 每条边都有一定的费用 让你选出最小的费用来将两座城市划成两部分

很典型的最小割问题 只是输出的要求是割边而不是花费 为了方便我这次用的模板是上一道题我魔改过的版本 求边时候比较好求

正好模板每次都会跑bfs 当发现已经切分成两部分返回结果 那么此时bfs的结果正好可以拿来利用 我们只需要对每条边 看一下两侧是不是属于两个集合的 若是那么这条边一定是割边了 输出即可

哦有一个问题是给的是双向边 所以建图时候需要双向建 输出结果时候记得去重或者干脆只考虑一个方向的即可

代码(交的时候VJ上UVA炸了…等下次不炸的时候看看有没有别的问题)好了过了

++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cstdio>
#include <vector>
#include <cstring>
#include<algorithm>
#include <queue>
using namespace std;
const int MAXV = 1050;
const int maxm=10050;
const int INF = 1<<30;
int edge;
int level[MAXV];
int iter[MAXV]; //当前弧，之前的已经没有用了
int head[MAXV];
struct edgenode
{
    int from;
    int to;//边的指向
    int cap;//边的容量
    int next;//链表的下一条边
} edges[maxm];
void init()
{
    edge=0;
    memset(head,-1,sizeof(head));
}
void addedge(int from, int to, int cap) {
    edges[edge].from=from;
    edges[edge].cap=cap;
    edges[edge].to=to;
    edges[edge].next=head[from];
    head[from]=edge++;
    edges[edge].from=to;
    edges[edge].cap=0;
    edges[edge].to=from;
    edges[edge].next=head[to];
    head[to]=edge++;
}

void bfs(int s) {
    memset(level, -1, sizeof level);
    std::queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (int i = head[v]; i !=-1; i=edges[i].next) {
            edgenode &e = edges[i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    if(iter[v]==0)
    {
        iter[v]=head[v];
    }
    for (int &i = iter[v]; i !=-1; i=edges[i].next) { // 注意i是引用 实现当前弧优化
        edgenode &e = edges[i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, std::min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                edges[i^1].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    for (; ;) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof iter);
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m),n+m)
    {
        init();
        for(int i=0;i<m;++i)
        {
            int u,v,cap;
            scanf("%d%d%d",&u,&v,&cap);
            addedge(u,v,cap);
            addedge(v,u,cap);
        }
        int res=maxflow(1,2);
        for(int i=0;i<edge;i+=2)
        {
            if(level[edges[i].from]!=-1&&level[edges[i].to]==-1)
            {
                printf("%d %d\n",edges[i].from,edges[i].to);
            }
        }
        printf("\n");
    }
    return 0;
}