SPOJ 287 Smart Network Administrator

坑哭了……
先是一个小地方初始化错误，tle了5发，看到下面说数据很多，还尝试开了输入挂……

然后数组开小，WA了n发

题意：
村通网系列。一个村子只有1号家庭有网络，现在有k家用户想要通网，为了网络质量，在一条街道上的每条网络都必须是不同的网线。问最少需要多少掉网线。（差不多就是这样的，颜色什么的就别管了……）

思路：
这道题我看完第一个想法就是二分，但是因为dinic的复杂度问题不是很敢写。搜了一下题解，居然真的是二分……众所周知dinic的复杂度上限为 O(n^2 * m) 如果是稠密图，最高可达 O(n^4) 二分最多9次，除开重新建图，数据最多500组，n最多500，也就是 500^5 ……

然而结果是 0.69 ，我也不知道是什么单位，在spoj刷题是几百年前了…… ，应该是 s 吧。

AC code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int n, m, k, st, en, idx;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int customer[maxn], head[maxn], from[maxn], to[maxn];

struct node {
    int to;
    int nxt;
    int flow;
} edges[2 * maxn * maxn];

inline void addEdge(int u, int v, int flow)
{
    edges[idx].to = v;
    edges[idx].flow = flow;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

inline bool scan_d(int& num)
{
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF)
        return false;
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else
        num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
    if (IsN)
        num = -num;
    return true;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u;
    while (l < r) {
        u = que[l++];
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que[r++] = v;
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= 2 * n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

inline void resetGraph(int len)
{
    memset(head, -1, sizeof head);
    idx = 0;
    for (int i = 0; i < m; i++) {
        addEdge(from[i], to[i], len);
        addEdge(to[i], from[i], len);
    }
    for (int i = 0; i < k; i++) {
        addEdge(customer[i], 0, 1);
        addEdge(0, customer[i], 0);
    }
}

int main()
{
    int T;
    scan_d(T);
    while (T--) {
        scan_d(n);
        scan_d(m);
        scan_d(k);
        st = 1, en = 0;
        for (int i = 0; i < k; i++)
            scan_d(customer[i]);
        for (int i = 0; i < m; i++) {
            scan_d(from[i]);
            scan_d(to[i]);
        }
        int l = 0, r = k, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            resetGraph(mid);
            if (dinic() >= k)
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}