无知 无求

0%

hdu4280 Island Transport

发表于 分类于 ，

本来读完题面以为是简单的网络流模板题…只是疑惑了一下为什么点的范围…这么大…然后发现常用的网络流板子过不去…
本来以为是vector初始化太慢了我强行改成手动管理..依旧t了

后来查了题解才明白这是需要另外一种算法…sap算法来优化网络流问题…过题的代码基本是按照题解来的就没啥可放的了…

超时代码

++
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
#include <cstdio>
#include <vector>
#include <cstring>
#include<algorithm>
#include <queue>
using namespace std;
const int MAXV = 100050;
const int maxm=100050;
const int INF = 1<<30;
int edge;
// struct Edge{ int to, cap, rev; };
// std::vector<Edge> G[MAXV];
int level[MAXV];
int iter[MAXV]; //当前弧，之前的已经没有用了
int head[MAXV];
struct edgenode
{
    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].cap=cap;
    edges[edge].to=to;
    edges[edge].next=head[from];
    head[from]=edge++;
    edges[edge].cap=0;
    edges[edge].to=from;
    edges[edge].next=head[to];
    head[to]=edge++;
    // G[from].push_back(Edge{to, cap, G[to].size()});
    // G[to].push_back(Edge{from, 0, G[from].size()-1});
}

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 = 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);
        //     }
        // }
        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;
    // for (int &i = iter[v]; i < G[v].size(); ++i) { // 注意i是引用 实现当前弧优化
    //     Edge &e = G[v][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;
    //             G[e.to][e.rev].cap += d;
    //             return d;
    //         }
    //     }
    // }
    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;
}
struct island
{
    int x,pos;
};
bool cmp(island a,island b)
{
    return a.x<b.x;
}
island lands[100030];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int N,M;
        scanf("%d%d",&N,&M);
        // for(int i=0;i<=N;++i)
        // {
        //     G[i].clear();
        // }
        init();
        for(int i=0;i<N;++i)
        {
            int x,y;
            scanf("%d%d",&lands[i].x,&y);
            lands[i].pos=i+1;
        }
        sort(lands,lands+N,cmp);
        for(int i=0;i<M;++i)
        {
            int u,v,t;
            scanf("%d%d%d",&u,&v,&t);
            addedge(u,v,t);
            addedge(v,u,t);
        }
        int res=maxflow(lands[0].pos,lands[N-1].pos);
        printf("%d\n",res);
    }
    return 0;
}