POJ 1815 Friendship

感觉网络流的题目总是莫名奇妙的卡在数组大小上
数组开小，既能WA，又能TLE，也真实神奇……

题意：
给你一张图，让你求出最小割集，并按照字典序输出。

思路：
老套的思路，那些discuss里的奇淫巧计看了一下貌似全都被推翻了……
枚举+最大流，尝试删点，如果流量减少，则为割点。

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

//#define DEBUG1 1

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

int n, idx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn];
int point[maxn];
int mat[maxn][maxn];
int ans[maxn];

struct node {
    int flow;
    int to;
    int nxt;
} edges[20005];

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

    edges[idx].to = u;
    edges[idx].flow = 0;
    edges[idx].nxt = head[v];
    head[v] = idx++;
}

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 > 0 && 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;
}

void CreateGraph()
{
    memset(head, -1, sizeof head);
    idx = 0;
    for (int i = 1; i <= n; i++) {
        point[i] = idx;
        addEdge(i, i + n, 1);
        for (int j = i + 1; j <= n; j++) {
            if (mat[i][j]) {
                addEdge(i + n, j, inf);
                addEdge(j + n, i, inf);
            }
        }
    }
#ifdef DEBUG1
    for (int u = 1; u <= 2 * n; u++) {
        printf("u : %d -----> ", u);
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            printf("%d ", edges[id].to);
        }
        puts("");
    }
#endif
}

int main()
{
    while (scanf("%d %d %d", &n, &st, &en) != EOF) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &mat[i][j]);
        if (mat[st][en] == 1) {
            puts("NO ANSWER!");
            continue;
        }
        st += n;
        CreateGraph();
        int max_flow = dinic(), top = 0;
        printf("%d\n", max_flow);
        for (int i = 1; i <= n && max_flow; i++) { 
            if (i == st - n || i == en)
                continue;
            CreateGraph();
            for (int j = 0; j < top; j++)
                edges[point[ans[j]]].flow = 0;
            edges[point[i]].flow = 0;
            int tmp = dinic();
            //printf("%d: flow %d\n", i, tmp);
            if (tmp != max_flow - 1)
                edges[point[i]].flow = 1;
            else {
                max_flow--;
                ans[top++] = i;
            }
        }
        for (int i = 0; i < top; i++)
            printf("%d%c", ans[i], i == top - 1 ? '\n' : ' ');
    }
    return 0;
}