[ZOJ2676]网络战争

发表于   |  

妈妈我终于会线性规划啦！

题目描述

Byteland的网络是由n个服务器和m条光纤组成的，每条光纤连接了两个服务器并且可以双向输送信息。这个网络中有两个特殊的服务器，一个连接到了全球的网络，一个连接到了总统府，它们的编号分别是1和N.

最近一家叫做Max Traffic的公司决定控制几条网络中的光纤，以使他们能够掌握总统府的的上网记录。为了到达这个目的，他们需要使所有从1号服务器到N号服务器的数据都经过至少一条他们所掌握的线路。

为了把这个计划付诸于行动，他们需要从这些线路的拥有者手中购买线路，每条线路都有对应的花费。自从公司的主要业务部是间谍活动而是家用宽带以后，经理就希望尽可能少的花费和尽可能高的回报。因此我们要使购买线路的平均值最小。

如果我们购买了k条线路，花费了c元，我们希望找到使c/k最小的方案。

输入格式

多组数据，每组数据第一行是两个整数n和m（1<=n<=100,1<=m<=400),代表服务器的个数和线路数

之后的m行，每行三个整数a，b，c，分别代表了这条线路所连接的服务器和购买这条线路的花费，花费都是正数且不会超过10^7

没有自边，没有重边，保证任意两点都是连通的。

最后一行为两个0

输出格式

每组数据的第一行是一个整数k，代表购买多少条线路

之后k个整数，代表购买线路的编号，编号是它们在输入文件被给处的顺序

每组数据之间有一个空行

样例输入

6 8
1 2 3
1 3 2
2 4 2
2 5 2
3 4 2
3 5 2
5 6 3
4 6 3
4 5
1 2 2
1 3 2
2 3 1
2 4 2
3 4 2
0 0

样例输出

4
3 4 5 6

3
1 2 3

Sol

网络流+分数规划例题，详见《最小割模型在信息学奥赛中的应用》
写了好久orz

Code

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#define Eps 1e-6
#define INF 1000000007
using namespace std;
#define maxn 410
#define maxm 1610
int x[maxm], y[maxm];
float z[maxm];
int S = 1, T, n, m;
struct Edge
{
    int u, v, l, nex;
    float f;
}ed[maxm];
int fir[maxn], e = 0;
void addedge(int u, int v, float f, int l){
    ed[++e].v = v;
    ed[e].u = u;
    ed[e].f = f;
    ed[e].l = e + l;
    ed[e].nex = fir[u];
    fir[u] = e;
}
queue <int> q;
int dis[maxn];
bool bfs(){
    memset(dis, -1, sizeof dis);
    q.push(S);
    dis[S] = 0;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = fir[u]; i; i = ed[i].nex) {
            int v = ed[i].v;
            if (fabs(ed[i].f) > Eps && dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    if (dis[T] != -1) return true;
    return false;
}

float find(int u, float mf = INF){
    if (u == T) return mf;
    float flow = 0;
    for (int i = fir[u]; i; i = ed[i].nex) {
        int v = ed[i].v;
        if (fabs(ed[i].f) > Eps && dis[v] == dis[u] + 1 && ( fabs(flow = find(v, min(mf, ed[i].f))) > Eps )) {
            ed[i].f -= flow;
            ed[ed[i].l].f += flow;
            return flow;
        }
    }
    return 0;
}

bool vis[maxn];
void dfs(int u){
    int i, v;
    for (int i = fir[u]; i; i = ed[i].nex) {
        v = ed[i].v;
        if (vis[v] || fabs(ed[i].f) < Eps) continue;
        vis[v] = true;
        dfs(v);
    }
}


float dinic(){
    float ret = 0, flow = 0;
    while (bfs()) {
        while (fabs(flow = find(S)) > Eps) {
            ret += flow;
        }  
    }
    return ret;
}
int num = 0;
int map[maxn][maxn];
bool flag[maxn];

bool MAIN(){
    scanf(""%d%d"", &n, &m);
    if (n == 0 && m == 0) return false;
    T = n; num = 0;
    float l = 0, r = 0;
    for (int i = 1; i <= m; i++){
        scanf(""%d%d%f"", &x[i], &y[i], &z[i]);
        map[x[i]][y[i]] = i;
        map[y[i]][x[i]] = i;
        r += z[i];
    }
    float R = 0;
    while (r - l >= Eps) {
        float L = (l + r) / 2.0;
        e = 0; memset(fir, 0, sizeof fir); memset(ed, 0, sizeof ed); memset(flag, 0, sizeof flag);           
        float ans = 0;
        num = 0;
        for (int i = 1; i <= m; i++){
            float w = z[i] - L;

            if (w < 0) {
                ans += w;
                flag[i] = true;
                num++;
                continue;
            }
            addedge(x[i], y[i], w, 1);            
            addedge(y[i], x[i], w, 1);
        }
        float x = dinic();
        ans += x;
        if (fabs(ans) < Eps) {
            R = L;
            break;
        }
        if (ans > 0) l = L; else r = L;  
    }   
    memset(vis, 0, sizeof vis);
    vis[S] = true;
    dfs(S);
    for (int i = 1; i <= e; i++) {
        int u = ed[i].u, v = ed[i].v;
        if (vis[u] && !vis[v] && fabs(ed[i].f) < Eps && !flag[map[u][v]]) {
            flag[map[u][v]] = true;
            num++;
        }
    }
    printf(""%d\n"", num);
    for (int i = 1; i <= m; i++) {
        if (flag[i]) printf(""%d "", i);
    }
    printf(""\n\n"");
    return true;
}


int main(){
freopen(""networkwar.in"", ""r"", stdin);
freopen(""networkwar.out"", ""w"", stdout);
    while (MAIN()) {
        memset(x, 0, sizeof x);
        memset(y, 0, sizeof y);
        memset(z, 0, sizeof z);
        memset(map, 0, sizeof map);
        memset(vis, 0, sizeof vis);
    }
    return 0;   
}