UVA-11167 Monkeys in the Emei Mountain（区间模型最大流+输出方案）

题目大意：有n只猴子，每只猴子都有一组参数(v,a,b)，表示这只猴子在时间段[a,b]之间必须要喝v个单位水，并且每个时间单位只能和一个单位水，每次至少喝一个单位。但是只有一个水池，并且这个水池最多只允许m只猴子同时喝水。问能否满足所有的猴子喝水，若能，输出任意一种可行的方案。

题目分析：将每个猴子和每个喝水区间视作节点。将每只猴子向它对应的区间连弧，容量为该区间上能喝水的总单位数；从源点向每只猴子建弧，容量为对应猴子的总需求量；从每个区间向汇点建弧，容量为该区间单位长度乘以m，表示在该区间最多允许有m只猴子同时喝水。求得最大流看是否能满足最大需求，如果能，则输出方案，其中，猴子节点连向区间节点的弧上的容量便是一种可行方案，最后要注意区间合并。

代码如下：

# 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=50005;

///////////////////////////////////

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 Monkey

{

    int v,l,r;

};

Monkey mon[105];

int n,m,sum,T[N];

vector<int>Time;

int getID(int x)

{

    return lower_bound(Time.begin(),Time.end(),x)-Time.begin();

}

int main()

{

    int cas=0;

    while(scanf("%d",&n)&&n)

    {

        scanf("%d",&m);

        sum=0;

        Time.clear();

        REP(i,1,n+1){

            scanf("%d%d%d",&mon[i].v,&mon[i].l,&mon[i].r);

            sum+=mon[i].v;

            Time.push_back(mon[i].l);

            Time.push_back(mon[i].r);

        }

        sort(Time.begin(),Time.end());

        vector<int>::iterator it=unique(Time.begin(),Time.end());

        Time.erase(it,Time.end());

        int len=Time.size();

        dinic.init(n+len+2,0,n+len+1);

        REP(i,1,n+1){

            dinic.addEdge(0,i,mon[i].v);

            int a=getID(mon[i].l);

            int b=getID(mon[i].r);

            REP(j,a,b) dinic.addEdge(i,j+n+1,Time[j+1]-Time[j]);

        }

        REP(j,0,len-1) dinic.addEdge(j+n+1,n+len+1,m*(Time[j+1]-Time[j]));

        int flow=dinic.MaxFlow();

        /*for(int i=0;i<dinic.edges.size();i+=2){

            Edge &e=dinic.edges[i];

            cout<<e.fr<<' '<<e.to<<' '<<e.cap<<' '<<e.fw<<endl;

        }*/

        if(flow!=sum){

            printf("Case %d: No\n",++cas);

        }else{

            printf("Case %d: Yes\n",++cas);

            REP(i,0,len) T[i]=Time[i];

            REP(i,1,n+1){

                vector<int>temp;

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

                    Edge &e=dinic.edges[dinic.G[i][j]];

                    if(e.fw<=0) continue;

                    int x=e.to-n-1;

                    temp.push_back(T[x]);

                    temp.push_back(min(Time[x+1],T[x]+e.fw));

                    T[x]+=e.fw;

                    if(T[x]>=Time[x+1]){

                        T[x]=Time[x]+T[x]-Time[x+1];

                        if(T[x]>Time[x]){

                            temp.push_back(Time[x]);

                            temp.push_back(T[x]);

                        }

                    }

                }

                sort(temp.begin(),temp.end());

                for(int j=0;j+1<temp.size();){

                    if(temp[j]==temp[j+1]){

                        temp.erase(temp.begin()+j);

                        temp.erase(temp.begin()+j);

                    }else

                        ++j;

                }

                printf("%d",temp.size()/2);

                for(int j=0;j<temp.size();j+=2)

                    printf(" (%d,%d)",temp[j],temp[j+1]);

                printf("\n");

            }

        }

    }

    return 0;

}

巴特西

UVA-11167 Monkeys in the Emei Mountain（区间模型最大流+输出方案）

最新文章

热门文章