HDU4183 Pahom on Water(来回走最大流，一个点只经过一次)

题意：

有n个圆，每个圆的中心和半径和一个频率都给定，只有一个频率最高的789为紫色，只有一个最低的400为红色，规则如下：

1.当两个圆严格相交时，且人是从红色到紫色的方向运动时可以由低频率向高频率移动

2.当两个圆严格相交时，且人是从紫色到红色的方向运动时可以由高频率向低频率运动

3.除了红色的圆以外，离开某个圆之后就会消失（即只能走一次）

思路：

如果一开始红色和紫色就相交，则存在合理方案。否则

本题要求是先从红点出发，经过紫点之后再返回红点，如果以红点作为源点，网络流算法不能先到达一个T，然后再到达另一个T，

所以不妨以紫点作为源点sp，红点作为tp，将点拆分成i和i+n，然后建边(i, i+n, 1), (sp, sp+n, 2)如果两个圆严格相交，设i的频率

大于j的频率，则(i+n, j, 1)反之(j+n, i, 1)，求出最大流为2则存在合理方案。把S(紫色) -> T(红色)的两个流中的一个流反向，就可以形成一个

T -> S -> T的方案。

#include <bits/stdc++.h>

using namespace std;

const int maxn =  + ;

const int inf = 0x3f3f3f3f;

struct point{

    double f;

    double x, y, r;

} p[maxn];

struct edge{

    int to, w, next;

} ed[maxn*maxn<<];

int k, n, sp, tp;

int head[maxn<<], tot, d[maxn<<], maxflow;

inline void init(){

    memset( head, -, sizeof(head) );

    tot = ;

}

inline double getlen2( const point a, const point b ){

    double x1 = a.x, x2 = b.x;

    double y1 = a.y, y2 = b.y;

    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);

}

inline bool judge(point a, point b){

    return getlen2(a, b) < (a.r+b.r)*(a.r+b.r);

}

inline void add( int u, int v, int w ){

    ed[++tot].to = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot;

    ed[++tot].to = u; ed[tot].w = ; ed[tot].next = head[v]; head[v] = tot;

}

inline bool bfs(){

    memset( d, , sizeof(d) );

    queue<int> q;

    d[sp] = ;

    q.push(sp);

    while( !q.empty() ){

        int x = q.front();

        q.pop();

        for( int i=head[x]; i!=-; i=ed[i].next ){

            int y = ed[i].to;

            if( ed[i].w && !d[y] ){

                d[y] = d[x] + ;

                q.push(y);

                if( y==tp ) return ;

            }

        }

    }

    return ;

}

inline int dfs( int x, int flow ){

    if( x==tp ) return flow;

    int res = flow, k;

    for( int i=head[x]; i!=-&&res; i=ed[i].next ){

        int y = ed[i].to;

        if( ed[i].w && d[y]==d[x]+ ){

            k = dfs( y, min( res, ed[i].w ) );

            if(!k) d[y] = ;

            ed[i].w -= k;

            ed[i^].w += k;

            res -= k;

        }

    }

    return flow - res;

}

inline void dinic(){

    int flow = maxflow = ;

    while( bfs() ){

        while( flow = dfs(sp, inf) ) maxflow += flow;

    }

}

int main(){

    // freopen("in.txt", "r", stdin);

    scanf("%d", &k);

    while( k-- ){

        scanf("%d", &n);

        init();

        for( int i=; i<=n; i++ ){

            scanf("%lf%lf%lf%lf", &p[i].f, &p[i].x, &p[i].y, &p[i].r);

            if( p[i].f==400.0 ) tp = i;

            else if( p[i].f==789.0 ) sp = i;

            else add( i, i+n,  );

        }

        if( judge( p[sp], p[tp] ) ){

            puts("Game is VALID");

            continue;

        }

        add( sp, sp+n,  );

        for( int i=; i<=n; i++ )

            for( int j=i+; j<=n; j++ ){

                if( judge(p[i], p[j]) ){

                    if( p[i].f<p[j].f ) add( j+n, i,  );

                    else add( i+n, j,  );

                }

            }

        dinic();

        // cout << maxflow << endl;

        if( maxflow>= ) puts("Game is VALID");

        else puts("Game is NOT VALID");

    }

    return ;

}

/*

Game is NOT VALID

Game is VALID

 */

巴特西

HDU4183 Pahom on Water(来回走最大流，一个点只经过一次)

最新文章

热门文章