HDU4280 (Island Transport)[网络流]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4280

这题是一道比较裸的网络流题，需要注意的是每条航线是双向的，连边时需要加上反向边。
另外这题非常卡时间，我用dinic超时了，换成了ISAP。

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int INF=0x3f3f3f3f,MAXN=100010,MAXM=400009;
struct Edge {
    int to,next,cap,flow;
}edge[MAXM];
int tot;
int head[MAXN];
int gap[MAXN],dep[MAXN],cur[MAXN];
void init() {
    tot=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw=0) {
    edge[tot].to=v;edge[tot].cap=w;edge[tot].flow=0;
    edge[tot].next=head[u];head[u]=tot++;
    edge[tot].to=u;edge[tot].cap=rw;edge[tot].flow=0;
    edge[tot].next=head[v];head[v]=tot++;
}
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 main() {
    int T;
    int x,y;
    int mnx,mxx;
    int u,v,cap;
    int s,t,n,m;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        init();
        mnx=INF;mxx=-INF;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&x,&y);
            if(x<mnx) {
                mnx=x;
                s=i;
            }
            if(x>mxx) {
                mxx=x;
                t=i;
            }
        }
        for(int i=0;i<m;i++) {
            scanf("%d%d%d",&u,&v,&cap);
            addedge(u,v,cap);
            addedge(v,u,cap);
        }
        int maxflow=sap(s,t,n);
        printf("%d\n",maxflow);
    }
}