hyz's blog
0%

kuangbin带你飞 专题十一 网络流 题解

发表于

kuangin带你飞专题十一 网络流 传送门
网络流问题 = 建模 + 高效模板

A. POJ 3436 ACM Computer Factory

最大流问题，需要拆点、打印路径。

B. POJ 3281 Dining

最大流问题，需要拆点。
经典建模思路：将牛拆点放在中间，然后左边连食物，右边连饮料。

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
156
157
158
159
160
161
// 经测试，ISAP比dinic快了不少

#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const double Eps=1e-7;

/************************************************************/
const int MAXN = 409;//点数的最大值
const int MAXM = N;//边数的最大值
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

int n, f, d, start, en, ff, dd, t;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d%d", &n, &f, &d)) {
        start = 0, en = f + 2 * n + d + 1;
        init();
        for(int i = 1; i <= f; i++)
            addedge(0, i, 1);
        for(int i = 1; i <= d; i++)
            addedge(f + 2 * n + i, en, 1);
        for(int i = 1; i <= n; i++)
            addedge(f + i, f + n + i, 1);
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &ff, &dd);
            for(int j = 0; j < ff; j++) {
                scanf("%d", &t);
                addedge(t, f + i, 1);
            }
            for(int j = 0; j < dd; j++) {
                scanf("%d", &t);
                addedge(f + n + i, f + 2 * n + t, 1);
            }
        }
        int ans = sap(start, en, en + 1);
        printf("%d\n", ans);
    }

    return 0;
}

C. POJ 1087 A Plug for UNIX

最大流问题，很容易想，但是需要细心，理解好题意，计算好节点个数。

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
#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const double Eps=1e-7;


/************************************************************************************/
/* dinic算法：解决最大流问题。
 * 时间复杂度为O(|E| * |V| * |V|)，不过，该算法在实际应用中速度非常快。
 *
 */

const int MAX_V = 509;

struct edge{int to, cap, rev; };

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from, int to, int cap){
    G[from].push_back((edge){to, cap, static_cast<int>(G[to].size())});
    G[to].push_back((edge){from, 0, static_cast<int>(G[from].size()-1)});
}

void bfs(int s){
    memset(level, -1, sizeof level);
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v=que.front(); que.pop();
        for(int i=0; i<G[v].size(); i++){
            edge &e=G[v][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;
    for(int &i=iter[v]; i<G[v].size(); i++){
        edge &e=G[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            int d=dfs(e.to, t, min(f, e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t){
    int flow=0;
    while(1){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter, 0, sizeof iter);
        int f;
        while((f=dfs(s, t, INF))>0)
            flow+=f;
    }
}

/************************************************************************************/

int start, en, n, m, k, tot;
string s, t, s1, s2;
map<string, int> ms, mt;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    start = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        cin >> s;
        if(!ms[s]) ms[s] = ++tot;
        add_edge(0, ms[s], 1);
    }
    scanf("%d", &m);
    en = 400 + m + 1;
    for(int i = 0; i < m; i++) {
        cin >> t >> s;
        if(!mt[t]) mt[t] = ++tot;
        if(!ms[s]) ms[s] = ++tot;
        add_edge(ms[s], mt[t], 1);
        add_edge(mt[t], en, 1);
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        cin >> s1 >> s2;
        if(!ms[s1]) ms[s1] = ++tot;
        if(!ms[s2]) ms[s2] = ++tot;
        add_edge(ms[s2], ms[s1], INF);
    }
    int ans = m - max_flow(start, en);
    printf("%d\n", ans);

    return 0;
}

D. POJ 2195 Going Home

最小费用最大流问题，也可以当成二分图最小权匹配问题来写。

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
156
157
158
159
160
161
162
163
164
165
166
167
#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double Eps=1e-7;


/************************************************************/
/* SPFA版最小费用最大流算法(Untested)
 * 最小费用最大流,求最大费用只需要取相反数,结果取相反数即可。
 * 点的总数为 N,点的编号 0 ~ N-1
 */
const int MAXN = 10000;
const int MAXM = 100000;
struct Edge{
    int to,next,cap,flow,cost;
}edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数,节点编号从 0 ∼ N-1
void init(int n){
    N = n;
    tol = 0;
    memset(head, -1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost){
    edge[tol].to = v;
    edge[tol].cap = cap;
    edge[tol].cost = cost;
    edge[tol].flow = 0;
    edge[tol].next = head[u];
    head[u] = tol++;
    edge[tol].to = u;
    edge[tol].cap = 0;
    edge[tol].cost = -cost;
    edge[tol].flow = 0;
    edge[tol].next = head[v];
    head[v] = tol++;
}
bool spfa(int s,int t){
    queue<int>q;
    for(int i = 0;i < N;i++){
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -1;i = edge[i].next){
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge
                    [i].cost )
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v]){
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t] == -1)return false;
    else return true;
}
//返回的是最大流,cost 存的是最小费用
int minCostMaxflow(int s,int t,int &cost){
    int flow = 0;
    cost = 0;
    while(spfa(s,t)){
        int Min = INF;
        for(int i = pre[t];i != - 1;i = pre[edge[i^1].to]){
            if(Min > edge[i].cap - edge[i].flow)
                Min = edge[i].cap - edge[i].flow;
        }
        for(int i = pre[t];i != - 1;i = pre[edge[i^1].to]){
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}
/************************************************************/

vector<pii> vm, vh;
int n, m, start, en, id, id1, cost;
char g[109][109];

int ID(int i, int j) {
    return i * m + j + 1;
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        if(!n && !m) break;
        start = 0;
        en = n * m + 1;
        init(en + 1);
        vm.clear();
        vh.clear();
        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(g[i][j] == 'm')
                    vm.push_back(pii(i, j));
                else if(g[i][j] == 'H')
                    vh.push_back(pii(i, j));
            }
        }
        for(vector<pii>::iterator it = vm.begin(); it != vm.end(); it++) {
            pii i = *it;
            id = ID(i.x, i.y);
            addedge(start, id, 1, 0);
            for(vector<pii>::iterator it1 = vh.begin(); it1 != vh.end(); it1++) {
                pii j = *it1;
                id1 = ID(j.x, j.y);
                cost = abs(i.x - j.x) + abs(i.y - j.y);
                addedge(id, id1, 1, cost);
            }
        }
        for(vector<pii>::iterator it = vh.begin(); it != vh.end(); it++) {
            pii i = *it;
            id = ID(i.x, i.y);
            addedge(id, en, 1, 0);
        }
        minCostMaxflow(start, en, cost);
        printf("%d\n", cost);
    }

    return 0;
}

E. POJ 2516 Minimum Cost

最小费用最大流问题，需要将每个物品分别处理，最后累加。假如直接将所有物品一起建图处理的话，不仅麻烦，而且会超时。
套路：把一个问题分成几个子问题来求解，可降低时间复杂度。

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
156
157
158
159
160
161
162
163
#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double Eps=1e-7;


/************************************************************/
/* SPFA版最小费用最大流算法(Tested 1 times)
 * 最小费用最大流,求最大费用只需要取相反数,结果取相反数即可。
 * 点的总数为 N,点的编号 0 ~ N-1
 */
const int MAXN = 10000;
const int MAXM = 100000;
struct Edge{
    int to,next,cap,flow,cost;
}edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int NN;//节点总个数,节点编号从 0 ∼ NN-1
void init(int n){
    NN = n;
    tol = 0;
    memset(head, -1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost){
    edge[tol].to = v;
    edge[tol].cap = cap;
    edge[tol].cost = cost;
    edge[tol].flow = 0;
    edge[tol].next = head[u];
    head[u] = tol++;
    edge[tol].to = u;
    edge[tol].cap = 0;
    edge[tol].cost = -cost;
    edge[tol].flow = 0;
    edge[tol].next = head[v];
    head[v] = tol++;
}
bool spfa(int s,int t){
    queue<int>q;
    for(int i = 0;i < NN;i++){
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -1;i = edge[i].next){
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge
                    [i].cost )
            {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v]){
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t] == -1)return false;
    else return true;
}
//返回的是最大流,cost 存的是最小费用
int minCostMaxflow(int s,int t,int &cost){
    int flow = 0;
    cost = 0;
    while(spfa(s,t)){
        int Min = INF;
        for(int i = pre[t];i != - 1;i = pre[edge[i^1].to]){
            if(Min > edge[i].cap - edge[i].flow)
                Min = edge[i].cap - edge[i].flow;
        }
        for(int i = pre[t];i != - 1;i = pre[edge[i^1].to]){
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}
/************************************************************/

int n, m, k, need, ans, cost, a[109][109], start, en, b[109][109], d, tot;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d%d", &n, &m, &k)) {
        if(!n) break;
        need = 0, tot = 0, ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < k; j++) {
                scanf("%d", a[i] + j);
                need += a[i][j];
            }
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < k; j++) {
                scanf("%d", b[i] + j);
            }
        }
        start = 0, en = n + m + 1;
        for(int o = 0; o < k; o++) {
            init(en + 1);
            for(int i = 0; i < m; i++) {
                addedge(start, i + 1, b[i][o], 0);
            }
            for(int i = 0; i < n; i++) {
                addedge(m + i + 1, en, a[i][o], 0);
            }
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    scanf("%d", &d);
                    addedge(j + 1, m + i + 1, INF, d);
                }
            }
            tot += minCostMaxflow(start, en, cost);
            ans += cost;
        }
        if(tot != need)
            printf("-1\n");
        else
            printf("%d\n", ans);
    }

    return 0;
}

F. POJ 1459 Power Network

最大流问题，题意有点难懂，输入需要点处理。

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
156
157
158
#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double Eps=1e-7;
const int N=1e5+9;


/************************************************************/
/* ISAP + bfs初始化 + 栈优化：超高效地解决最大流问题
 * 注意修改MAXN和MAXM成适合的大小，以提高时间效率
 */
const int MAXN = 109;//点数的最大值
const int MAXM = 20409;//边数的最大值
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

int n, np, nc, m, start, en, u, v, cap;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d%d%d", &n, &np, &nc, &m)) {
        init();
        start = 0, en = n + 1;
        for(int i = 0; i < m; i++) {
            scanf(" (%d,%d)%d", &u, &v, &cap);
            addedge(u + 1, v + 1, cap);
        }
        for(int i = 0; i < np; i++) {
            scanf(" (%d)%d", &u, &cap);
            addedge(start, u + 1, cap);
        }
        for(int i = 0; i < nc; i++) {
            scanf(" (%d)%d", &u, &cap);
            addedge(u + 1, en, cap);
        }
        int ans = sap(start, en, en + 1);
        printf("%d\n", ans);
    }

    return 0;
}

G. HDU 4280 Island Transport

最大流问题，很裸，但是直接上dinic算法的话，会超时，需要用带优化的ISPA算法。

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
156
157
158
159
#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const double Eps=1e-7;


const int MAXN = 100010;//点数的最大值
const int MAXM = 400010;//边数的最大值
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}

int start, en, mifix, mafix, T, n, m, x, u, v, cap;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);} 
    cin >> T;
    while(T--) {
        scanf("%d%d", &n, &m);
        init();
        start = -1, mifix = INF, en = -1, mafix = -INF;
        for(int i = 0; i < n; i++) {
            scanf("%d%*d", &x);
            if(x < mifix) {
                start = i;
                mifix = x;
            }
            if(x > mafix) {
                en = i;
                mafix = x;
            }
        }
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &cap);
            u--, v--;
            addedge(u, v, cap);
            addedge(v, u, cap);
        }
        int ans = sap(start, en, n);
        printf("%d\n", ans);
    }

    return 0;
}

H. HDU 4292 Food

最大流问题，是POJ 3281的升级版，灵活修改一下边权即可。

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
156
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double Eps=1e-7;
const int N=1e5+9;


/************************************************************/
/* ISAP + bfs初始化 + 栈优化：超高效地解决最大流问题
 * 注意修改MAXN和MAXM成适合的大小，以提高时间效率
 */
const int MAXN = 1009;//点数的最大值
const int MAXM = 400010;//边数的最大值，注意反向边也要算进去，也就是说要乘以2
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

int n, f, d, start, en, t;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d%d", &n, &f, &d)) {
        init();
        start = 0, en = f + 2 * n + d + 1;
        for(int i = 1; i <= f; i++) {
            scanf("%d", &t);
            addedge(start, i, t);
        }
        for(int i = 1; i <= d; i++) {
            scanf("%d", &t);
            addedge(f + 2 * n + i, en, t);
        }
        for(int i = 1; i <= n; i++) {
            addedge(f + i, f + n + i, 1);
        }
        for(int i = 1; i <= n; i++) {
            getchar();
            for(int j = 1; j <= f; j++) {
                if(getchar() == 'Y') {
                    addedge(j, f + i, 1);
                }
            }
        }
        for(int i = 1; i <= n; i++) {
            getchar();
            for(int j = 1; j <= d; j++) {
                if(getchar() == 'Y') {
                    addedge(f + n + i, f + 2 * n + j, 1);
                }
            }
        }

        int ans = sap(start, en, en + 1);
        printf("%d\n", ans);
    }

    return 0;
}

I. HDU 4289 Control

最小割问题，需要拆点。

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double Eps=1e-7;
const int N=1e5+9;

/************************************************************/
/* ISAP + bfs初始化 + 栈优化：超高效地解决最大流问题
 * 注意修改MAXN和MAXM成适合的大小，以提高时间效率
 */
const int MAXN = 409;//点数的最大值
const int MAXM = 400010;//边数的最大值，注意反向边也要算进去，也就是说要乘以2
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

int n, m, start, en, d, u, v;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        init();
        scanf("%d%d", &start, &en);
        en += n;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &d);
            addedge(i, i + n, d);
        }
        while(m--) {
            scanf("%d%d", &u, &v);
            addedge(u + n, v, INF);
            addedge(v + n, u, INF);
        }
        int ans = sap(start, en, 2 * n + 1);
        printf("%d\n", ans);
    }

    return 0;
}

J. UVA 10480 Sabotage

最小割问题，要求输出割边。

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 9223372036854775807;
const double Eps = 1e-7;
const int N = 1e5+9;


/************************************************************/
/* EK算法：解决最大流问题，使用邻接矩阵，可打印路径(Tested 0 times)
 * 初始化：g[][], start, end, nn
 * 时间复杂度：O(|V| * |E| * |E|)
 */
const int MAXN = 110;
int g[MAXN][MAXN];//存边的容量，没有边的初始化为0
int path[MAXN], flow[MAXN], start, en;
int nn;//点的个数，编号0-nn.nn包括了源点和汇点

queue<int>q;
int bfs() {
    int i,t;
    memset(flow, 0, sizeof flow);
    while(!q.empty()) q.pop();//把清空队列
    memset(path, -1, sizeof path);//每次搜索前都把路径初始化成-1
    path[start] = 0;
    flow[start] = INF;//源点可以有无穷的流流进
    q.push(start);
    while(!q.empty()) {
        t = q.front();
        q.pop();
        if(t == en) break;
        //枚举所有的点，如果点的编号起始点有变化可以改这里
        for(i = 1;i <= nn; i++) {
            if(i != start && path[i] == -1 && g[t][i]) {
                flow[i] = min(flow[t], g[t][i]);
                q.push(i);
                path[i] = t;
            }
        }
    }
    if(path[en] == -1) return -1;//找不到增广路径了
    return flow[en];
}
int max_flow() {
    int max_flow = 0;
    int step, now, pre;
    while((step = bfs()) != -1) {
        max_flow += step;
        now = en;
        while(now != start) {
            pre = path[now];
            g[pre][now] -= step;
            g[now][pre] += step;
            now = pre;
        }
    }
    return max_flow;
}
/************************************************************/

pii a[N];
int n, m, w;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m) && n) {
        memset(g, 0, sizeof g);
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &a[i].x, &a[i].y, &w);
            g[a[i].x][a[i].y] = g[a[i].y][a[i].x] = w;
        }
        start = 1, en = 2, nn = n;
        max_flow();
        for(int i = 0; i < m; i++) {
            if((flow[a[i].x] && !flow[a[i].y]) || (flow[a[i].y] && !flow[a[i].x]))
                printf("%d %d\n", a[i].x, a[i].y);
        }
        printf("\n");
    }

    return 0;
}

K. HDU 2732 Leapin’ Lizards

最大流问题，需要拆点。

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 9223372036854775807;
const double Eps = 1e-7;
const int N = 1e5+9;



/************************************************************/
/* ISAP + bfs初始化 + 栈优化：超高效地解决最大流问题(Tested 3+ times)
 * 注意修改MAXN和MAXM成适合的大小，以提高时间效率
 */
const int MAXN = 1001;//点数的最大值
const int MAXM = 20009;//边数的最大值，注意反向边也要算进去，也就是说要乘以2
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

char g[29][29];
int n, m, d, start, en, T, kase;

int ID(int i, int j) {
    return (i - 1) * m + j;
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &d);
        for(int i = 1; i <= n; i++) {
            scanf("%s", g[i] + 1);
        }
        m = strlen(g[1] + 1);
        init();
        start = 0, en = 2 * n * m + 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(g[i][j] == '0') continue;
                addedge(ID(i, j), n * m + ID(i, j), g[i][j] - '0');
                for(int x = -d; x <= d; x++) {
                    for(int y = -d; y <= d; y++) {
                        if(!x && !y) continue;
                        if(abs(x) + abs(y) > d) continue;
                        int nx = i + x, ny = j + y;
                        if(nx < 1 ||  nx > n || ny < 1 || ny > m) {
                            addedge(n * m + ID(i, j), en, 3);
                        }
                        else
                            addedge(n * m + ID(i, j), ID(nx, ny), 3);
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%s", g[i] + 1);
            for(int j = 1; j <= m; j++) {
                if(g[i][j] == 'L') {
                    ans++;
                    addedge(start, ID(i, j), 1);
                }
            }
        }
        ans -= sap(start, en, en + 1);
        if(ans == 0) {
            printf("Case #%d: no lizard was left behind.\n", ++kase);
        }
        else if(ans == 1) {
            printf("Case #%d: %d lizard was left behind.\n", ++kase, ans);
        }
        else {
            printf("Case #%d: %d lizards were left behind.\n", ++kase, ans);
        }
    }

    return 0;
}

L. HDU 3338 Kakuro Extension

行列模型的最大流问题，比较神奇。
还需要处理一下最小下界流量的限制。

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 9223372036854775807;
const double Eps = 1e-7;
const int N = 1e5+9;


/************************************************************/
/* ISAP + bfs初始化 + 栈优化：超高效地解决最大流问题(Tested 6 times)
 * 注意修改MAXN和MAXM成适合的大小，以提高时间效率
 * 时间复杂度：O(|E| * |V| * |V|)
 */
const int MAXN = 100010;//点数的最大值
const int MAXM = 400010;//边数的最大值，注意反向边也要算进去，也就是说要乘以2
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
// start起点，end为终点，nodeNum为顶点数，一般为en+1，注意en不为最后一个顶点的情况！
int sap(int start,int end,int nodeNum) {
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

int n, m, lx[109][109], ly[109][109], num[10009], cnt, id[109][109];
char s[109][109][9];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        cnt = 0;
        memset(lx, 0, sizeof lx);
        memset(ly, 0, sizeof ly);
        memset(num, 0, sizeof num);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                scanf("%s", s[i][j]);
                if(strcmp(s[i][j], ".......") == 0) {
                    if(j == 0 || lx[i][j - 1] == 0)
                        lx[i][j] = ++cnt;
                    else
                        lx[i][j] = cnt;
                    num[cnt]++;
                }
            }
        }
        for(int j = 0; j < m; j++) {
            for(int i = 0; i < n; i++) {
                if(strcmp(s[i][j], ".......") == 0) {
                    if(i == 0 || lx[i - 1][j] == 0)
                        ly[i][j] = ++cnt;
                    else
                        ly[i][j] = cnt;
                    num[cnt]++;
                }
            }
        }
        init();
        int start = 0, en = cnt + 1, nodeNum = en + 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(strcmp(s[i][j], ".......") == 0) {
                    id[i][j] = tol;
                    addedge(lx[i][j], ly[i][j], 8);
                }
                if(s[i][j][3] != '\\')
                    continue;
                if(s[i][j][0] != 'X') {
                    int t = (s[i][j][0] - '0') * 100 + (s[i][j][1] - '0') * 10
                        + (s[i][j][2] - '0');
                    addedge(ly[i + 1][j], en, t - num[ly[i + 1][j]]);
                }
                if(s[i][j][4] != 'X') {
                    int t = (s[i][j][4] - '0') * 100 + (s[i][j][5] - '0') * 10
                        + (s[i][j][6] - '0');
                    addedge(start, lx[i][j + 1], t - num[lx[i][j + 1]]);
                }
            }
        }
        sap(start, en, nodeNum);
        //cout << t << endl;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(j) putchar(' ');
                if(strcmp(s[i][j], ".......") == 0) {
                    putchar('0' + edge[id[i][j]].flow + 1);
                }
                else {
                    putchar('_');
                }
            }
            putchar('\n');
        }
    }

    return 0;
}

M. HDU 3605 Escape

最大流问题，直接建流量为1的图会TLE，需要把同种类型的人看做一个点，然后建流量等于人数的边。

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 9223372036854775807;
const double Eps = 1e-7;
const int N = 1e5+9;


/************************************************************/
/* ISAP + bfs初始化 + 栈优化：超高效地解决最大流问题(Tested 4 times)
 * 注意修改MAXN和MAXM成适合的大小，以提高时间效率
 */
const int MAXN = 100029;//点数的最大值
const int MAXM = MAXN * 23;//边数的最大值，注意反向边也要算进去，也就是说要乘以2
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(int t){
    tol = 0;
    memset(head,-1,sizeof(int) * t);
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

int n, m, start, en, d, cnt[N];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        start = 0, en = (1 << m) + m;
        memset(cnt, 0, sizeof(int) * (1 << m));
        init(en + 1);
        for(int i = 0; i < n; i++) {
            int sum = 0;
            for(int j = 0; j < m; j++) {
                scanf("%d", &d);
                if(d) sum += 1 << j;
            }
            cnt[sum]++;
        }
        int up = 1 << m;
        for(int i = 1; i < up; i++) {
            addedge(start, i, cnt[i]);
            for(int j = 0; j < m; j++) {
                if(i & (1 << j)) {
                    addedge(i, up + j, cnt[i]);
                }
            }
        }
        for(int i = 0; i < m; i++) {
            scanf("%d", &d);
            addedge(up + i, en, d);
        }
        int ans = sap(start, en, en + 1);
        if(ans == n)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}

N. HDU 3081 Marriage Match II

最大流问题 + 二分。

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 9223372036854775807;
const double Eps = 1e-7;
const int N = 1e5+9;


/************************************************************/
/* ISAP + bfs初始化 + 栈优化：超高效地解决最大流问题(Tested 4 times)
 * 注意修改MAXN和MAXM成适合的大小，以提高时间效率
 */
const int MAXN = 209;//点数的最大值
const int MAXM = 20409;//边数的最大值，注意反向边也要算进去，也就是说要乘以2
struct Edge{
    int to,next,cap,flow;
}edge[MAXM], edget[MAXM];//注意是 MAXM
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init(){
    tol = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
    edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
    edge[tol].next = head[u]; head[u] = tol++;
    edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
    edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head,sizeof(head));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge[S[i]].cap - edge[S[i]].flow){
                    Min = edge[S[i]].cap - edge[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge[S[i]].flow += Min;
                edge[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge[i].next){
            v = edge[i].to;
            if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u]; i != -1; i = edge[i].next)
            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
            {
                Min = dep[edge[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

int fa[N];

int find(int u) {
    return fa[u] == u ? u : fa[u] = find(fa[u]);
}

void uf(int u, int v) {
    fa[find(u)] = fa[find(v)];
}

int T, n, m, k, u, v;
int headt[N];
vi to[N], too[N];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &m, &k);
        init();
        int start = 0, en = 2 * n + 1;
        for(int i = 1; i <= n; i++) {
            to[i].clear();
            too[i].clear();
            fa[i] = i;
        }
        while(m--) {
            scanf("%d%d", &u, &v);
            to[u].push_back(v);
        }
        while(k--) {
            scanf("%d%d", &u, &v);
            uf(u, v);
        }
        for(int i = 1; i <= n; i++) {
            int fa = find(i);
            for(auto j: to[i]) {
                too[fa].push_back(j);
            }
        }
        for(int i = 1; i <= n; i++) {
            sort(too[i].begin(), too[i].end());
            too[i].resize(unique(too[i].begin(), too[i].end()) - too[i].begin());
        }
        for(int i = 1; i <= n; i++) {
            int fa = find(i);
            for(auto j: too[fa]) {
                addedge(i, n + j, 1);
            }
        }
        int tolt = tol;
        memcpy(headt, head, sizeof head);
        memcpy(edget, edge, sizeof edge);
        int l = 0, r = n + 1;
        while(l + 1 != r) {
            int mid = l + (r - l) / 2;
            memcpy(head, headt, sizeof(int) * (en + 1));
            memcpy(edge, edget, sizeof(Edge) * (tol + 1));
            tol = tolt;
            for(int i = 1; i <= n; i++) {
                addedge(start, i, mid);
                addedge(n + i, en, mid);
            }
            int t = sap(start, en, en + 1);
            if(t == n * mid)
                l = mid;
            else
                r = mid;
        }
        printf("%d\n", l);
    }

    return 0;
}

O. HDU 3416 Marriage Match IV

最大流问题 + 最短路问题。

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 9223372036854775807;
const double Eps = 1e-7;
const int N = 1e5+9;

int head[2][1009], tot;

struct Edge {
    int v, c, next;
    Edge () {}
    Edge (int v, int c, int next): v(v), c(c), next(next) {}
}edge[2 * N];

void addedge(int u, int v, int c, int ty) {
    edge[tot] = Edge{v, c, head[ty][u]};
    head[ty][u] = tot++;
}

void init() {
    memset(head, -1, sizeof head);
    tot = 0;
}

/************************************************************/
/* dijkstra算法：解决最短路问题(Tested 0 times)
 * 前向心存图
 */
const int MAX_V=10009;
int d[2][MAX_V];

void dijkstra(int s, int ty) {
    priority_queue<pii, vector<pii>, greater<pii> > que;
    d[ty][s] = 0;
    que.push(pii(0, s));
    while(!que.empty()) {
        pii p = que.top(); que.pop();
        int u = p.second;
        if(d[ty][u] < p.first) continue;
        for(int i = head[ty][u]; ~i; i = edge[i].next) {
            Edge e = edge[i];
            if(d[ty][e.v] > d[ty][u] + e.c) {
                d[ty][e.v] = d[ty][u] + e.c;
                que.push(pii(d[ty][e.v], e.v));
            }
        }
    }
}
/************************************************************/

/************************************************************/
/* ISAP + bfs初始化 + 栈优化：超高效地解决最大流问题(Tested 5 times)
 * 注意修改MAXN和MAXM成适合的大小，以提高时间效率
 * 时间复杂度：O(|E| * |V| * |V|)
 */
const int MAXN = 1009;//点数的最大值
const int MAXM = 200009;//边数的最大值，注意反向边也要算进去，也就是说要乘以2
struct Edge1{
    int to,next,cap,flow;
}edge1[MAXM];//注意是 MAXM
int tol;
int head1[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init1(){
    tol = 0;
    memset(head1,-1,sizeof(head1));
}
void addedge1(int u,int v,int w,int rw = 0){
    edge1[tol].to = v; edge1[tol].cap = w; edge1[tol].flow = 0;
    edge1[tol].next = head1[u]; head1[u] = tol++;
    edge1[tol].to = u; edge1[tol].cap = rw; edge1[tol].flow = 0;
    edge1[tol].next = head1[v]; head1[v] = tol++;
}
int Q[MAXN];
void BFS(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0] = 1;
    int front = 0, rear = 0;
    dep[end] = 0;
    Q[rear++] = end;
    while(front != rear){
        int u = Q[front++];
        for(int i = head1[u]; i != -1; i = edge1[i].next){
            int v = edge1[i].to;
            if(dep[v] != -1)continue;
            Q[rear++] = v;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
}
int S[MAXN];
int sap(int start,int end,int N){
    BFS(start,end);
    memcpy(cur,head1,sizeof(head1));
    int top = 0;
    int u = start;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            int inser;
            for(int i = 0;i < top;i++)
                if(Min > edge1[S[i]].cap - edge1[S[i]].flow){
                    Min = edge1[S[i]].cap - edge1[S[i]].flow;
                    inser = i;
                }
            for(int i = 0;i < top;i++){
                edge1[S[i]].flow += Min;
                edge1[S[i]^1].flow -= Min;
            }
            ans += Min;
            top = inser;
            u = edge1[S[top]^1].to;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u]; i != -1; i = edge1[i].next){
            v = edge1[i].to;
            if(edge1[i].cap - edge1[i].flow && dep[v]+1 == dep[u]){
                flag = true;
                cur[u] = i;
                break;
            }
        }
        if(flag){
            S[top++] = cur[u];
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head1[u]; i != -1; i = edge1[i].next)
            if(edge1[i].cap - edge1[i].flow && dep[edge1[i].to] < Min)
            {
                Min = dep[edge1[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min + 1;
        gap[dep[u]]++;
        if(u != start)u = edge1[S[--top]^1].to;
    }
    return ans;
}
/************************************************************/

int T, n, m, u, v, c[N];
pii a[N];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    scanf("%d", &T);
    while(T--) {
        init();
        scanf("%d%d", &n, &m);
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, c + i);
            a[i] = pii(u, v);
            addedge(u, v, c[i], 0);
            addedge(v, u, c[i], 1);
        }
        scanf("%d%d", &u, &v);
        memset(d, INF, sizeof d);
        dijkstra(u, 0);
        dijkstra(v, 1);
        init1();
        int start = 0, en = v;
        for(int i = 0; i < m; i++) {
            if(d[0][a[i].x] + c[i] + d[1][a[i].y] == d[0][v]) {
                addedge1(a[i].x, a[i].y, 1);
            }
        }
        addedge1(start, u, INF);
        printf("%d\n", sap(start, en, n + 1));
    }

    return 0;
}