网络流(二)----最大流Dinic算法

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 40002;

struct Node
{
    int to, flow, next;
}edge[maxn * 8];

int n, m;
int S, T, tot;
int q[maxn];
int dis[maxn]; //记录层次
int pre[maxn], rec[maxn], head[maxn];
bool block[maxn];

inline void Add_edge(int a, int b, int c)
{
    edge[tot].to = b; edge[tot].flow = c; edge[tot].next = head[a];
    head[a] = tot++;
    edge[tot].to = a; edge[tot].flow = 0; edge[tot].next = head[b];
    head[b] = tot++;
}

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

void BFS()
{
    int i;
    int h = 0, t = 0;
    memset(dis, INF, sizeof(dis));
    q[h] = S;
    dis[S] = 0;
    while(h <= t)
    {
        int u = q[h++];
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if(dis[v] == INF && edge[i].flow)
            {
                dis[v] = dis[u] + 1;
                q[++t] = v;
            }
        }
    }
}

int Dinic()
{
    int i, j;
    int top = S, MaxFlow = 0, mins = INF;
    pre[S] = S;
    BFS();
    memset(block, 0, sizeof(block));
    while(dis[T] != INF)
    {
        for(i = head[top]; i != -1; i = edge[i].next)
        {
            if(edge[i].flow && dis[top]+1 == dis[edge[i].to] && !block[edge[i].to])
                break;
        }
        if (i != -1)
        {
            j = edge[i].to;
            mins = min(mins, edge[i].flow);
            pre[j] = top;
            rec[j] = i;
            top = j;
            if(top == T)
            {
                i = -1;
                MaxFlow += mins;
                for(; top != S; top = pre[top])
                {
                    edge[rec[top]].flow -= mins;
                    edge[rec[top]^1].flow += mins;
                    if(!edge[rec[top]].flow) 
                    {
                        i = top;
                    }
                }
                if(i != -1)
                {
                    i = pre[i];
                    mins = INF;
                    for(j = i; j != S; j = pre[j])
                    {
                        mins = min(mins, edge[rec[j]].flow);
                    }
                    top = i;
                }
            }
        }
        else
        {
            block[top] = true;
            top = pre[top];
            if(block[S])
            {
                BFS();
                memset(block, 0, sizeof(block));
            }
        }
    }
    return MaxFlow;
}

struct Pad
{
    double x, y, rad;
    double fre;
}pad[maxn];

bool cmp(Pad A, Pad B)
{
    return A.fre < B.fre;
}

int main()
{
    int test, a, b;
    scanf("%d", &test);
    while(test--)
    {
        Init();
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%lf %lf %lf %lf", &pad[i].fre, &pad[i].x, &pad[i].y, &pad[i].rad);
        }
        sort(pad+1, pad+n+1, cmp);

        for(int i = 1; i <= n; i++)
        {
            //printf("%d-->%lf %lf %lf %lf
", i, pad[i].fre, pad[i].x, pad[i].y, pad[i].rad);
            for(int j = i + 1; j <= n; j++)
            {
                if((pad[j].x-pad[i].x) * (pad[j].x-pad[i].x) + (pad[j].y-pad[i].y) * (pad[j].y-pad[i].y)
                        < (pad[i].rad + pad[j].rad) * (pad[i].rad + pad[j].rad))
                {
                    Add_edge(i, j, 1);
                }
            }
        }
        S = 1; T = n;
        a = Dinic();
        Init();
        for(int i = n; i >= 1; i--)
        {
            for(int j = i - 1; j >= 1; j--)
            {
                if((pad[j].x-pad[i].x) * (pad[j].x-pad[i].x) + (pad[j].y-pad[i].y) * (pad[j].y-pad[i].y)
                        < (pad[i].rad + pad[j].rad) * (pad[i].rad + pad[j].rad))
                {
                    Add_edge(i, j, 1);
                }
            }
        }
        S = n; T= 1;
        b = Dinic();
        if(a>1 && b>1) puts("Game is VALID");
        else puts("Game is NOT VALID");
    }
    return 0;
}