UVALive-3972 March of the Penguins （最大流：节点容量）

题目大意：有n个带有裂缝的冰块。已知每个冰块的坐标和已经站在上面的企鹅数目，每当一个企鹅从一个冰块a跳到另一个冰块b上的时候，冰块a上的裂缝便增大一点，还知道每个冰块上最多能被跳跃的次数。所有的企鹅都想聚集在同一个冰块上并且都不想掉进水里，如果给出每只企鹅能跳跃的最大距离D，问哪几个冰块能让所有的企鹅聚集在一起？

题目分析：枚举所有的冰块，依次判断其是否满足题意。将每一个冰块视作一个节点，以冰块间企鹅能否跳跃建边，得到一张节点带有容量的图。对于节点容量的图拆点。以当前枚举的冰块为汇点t，增加源点s，从s向所有的冰块连一条弧，容量为冰块上起始的企鹅数目，将每个冰块拆开后的内弧的容量置为该冰块所有承受的最大跳跃次数。如果最大流等于企鹅总数，则当前枚举的冰块是可以的。

代码如下：

# include<iostream>

# include<cstdio>

# include<cmath>

# include<string>

# include<vector>

# include<list>

# include<set>

# include<map>

# include<queue>

# include<cstring>

# include<algorithm>

using namespace std;

# define LL long long

# define REP(i,s,n) for(int i=s;i<n;++i)

# define CL(a,b) memset(a,b,sizeof(a))

# define CLL(a,b,n) fill(a,a+n,b)

const double inf=1e30;

const int INF=1<<30;

const int N=1000;

struct Edge

{

    int fr,to,cap,fw;

    Edge(int _fr,int _to,int _cap,int _fw):fr(_fr),to(_to),cap(_cap),fw(_fw){}

};

struct Dinic{

    vector<Edge>edges;

    vector<int>G[N];

    int d[N],vis[N],cur[N];

    int s,t;

    void init(int n,int s,int t){

        this->s=s,this->t=t;

        REP(i,0,n) G[i].clear();

        edges.clear();

    }

    void addEdge(int u,int v,int cap)

    {

        edges.push_back(Edge(u,v,cap,0));

        edges.push_back(Edge(v,u,0,0));

        int len=edges.size();

        G[u].push_back(len-2);

        G[v].push_back(len-1);

    }

    bool BFS()

    {

        CL(vis,0);

        d[s]=0;

        vis[s]=1;

        queue<int>q;

        q.push(s);

        while(!q.empty()){

            int x=q.front();

            q.pop();

            REP(i,0,G[x].size()){

                Edge &e=edges[G[x][i]];

                if(!vis[e.to]&&e.cap>e.fw){

                    d[e.to]=d[x]+1;

                    vis[e.to]=1;

                    q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int DFS(int x,int a)

    {

        if(x==t||a==0) return a;

        int flow=0,f;

        for(int &i=cur[x];i<G[x].size();++i){

            Edge &e=edges[G[x][i]];

            if(d[e.to]==d[x]+1&&(f=DFS(e.to,min(a,e.cap-e.fw)))>0){

                e.fw+=f;

                edges[G[x][i]^1].fw-=f;

                flow+=f;

                a-=f;

                if(a==0) break;

            }

        }

        return flow;

    }

    int MaxFlow()

    {

        int flow=0;

        while(BFS()){

            CL(cur,0);

            flow+=DFS(s,INF);

        }

        return flow;

    }

};

Dinic dinic;

struct Floe

{

    int x,y,n,m;

};

Floe f[N];

int ans[N],total;

double D;

double dist(int i,int j)

{

    return sqrt(1.0*(f[i].x-f[j].x)*(f[i].x-f[j].x)+1.0*(f[i].y-f[j].y)*(f[i].y-f[j].y));

}

bool judge(int n,int m,int t)

{

    dinic.init(n,0,t);

    REP(i,1,m+1){

        dinic.addEdge(0,i*2-1,f[i].n);

        dinic.addEdge(i*2-1,i*2,f[i].m);

        REP(j,1,m+1){

            if(i==j) continue;

            if(dist(i,j)<=D) dinic.addEdge(2*i,j*2-1,INF);

        }

    }

    return dinic.MaxFlow()==total;

}

int main()

{

    int T,n,m;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%lf",&m,&D);

        dinic.init(m*2+2,0,m*2+1);

        total=0;

        REP(i,1,m+1){

            scanf("%d%d%d%d",&f[i].x,&f[i].y,&f[i].n,&f[i].m);

            total+=f[i].n;

        }

        ans[0]=0;

        REP(i,1,m+1) if(judge(m*2+2,m,i*2-1)) ans[++ans[0]]=i;

        if(ans[0]==0) printf("-1\n");

        else REP(i,1,ans[0]+1) printf("%d%c",ans[i]-1,(i==ans[0])?'\n':' ');

    }

    return 0;

}

巴特西

UVALive-3972 March of the Penguins （最大流：节点容量）

最新文章

热门文章