【poj1149】PIGS

2015.05.26 19:28 Tue | 18次阅读 | 旧日oi | 固定链接 | 源码

题目大意:有n个猪圈,每个猪圈有一些猪,按顺序来m个顾客,每个顾客可以打开一些猪圈,并且最多买一定数量的猪,被打开的猪圈的猪可以自由流通,问最多能卖出多少猪。猪圈<=1000,人数<=100
题解
算法一:建立n层,每层m个点,代表每一轮的猪圈,第i个顾客向汇点连容量为购买上限的边,并且和第i层能打开的猪圈连容量inf的边原点和第一层的猪圈连容量为猪的个数的边。除最后一层,每层的每个点向下一层能转移的点(包含自身)连容量为inf的边。然后dinic()。点数10w,不好。
算法二:源点向每个猪圈的第一个顾客连容量为猪的数量的边,每个猪圈的第i个顾客向第i+1个顾客连边,每个顾客向汇点连容量为购买上限的边。可以这样理解:如果一个顾客打开了猪圈h,那么他打开的所有猪圈里的猪都可以被换到h中,而这些猪都有可能被下一个打开h猪圈的人买走,所以要在这两个顾客间连inf的边。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,S,T;
int w[1005];
vector<int> v[1005];
struct edge{
    int to,next,flow;
}e[20000];
int h[105],tp;
void ae(int u,int v,int w)
{
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    h[u]=tp++;
}
void add(int u,int v,int w)
{
    ae(u,v,w);
    ae(v,u,0);
}
queue<int> q;
int dis[105];
bool bfs()
{
    while(!q.empty()) q.pop();q.push(S);
    memset(dis,0,sizeof(dis));dis[S]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==T) return 1;
            q.push(v);
        }
    }
    return 0;
}
int dfs(int u,int limit)
{
    if(u==T) return limit;
    int cost=0,tmp;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(e[i].flow,limit-cost));
        if(tmp)
        {
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(cost==limit)break;
        }
        else dis[v]=-1;
    }
    return cost;
}
int dinic()
{
    int ret=0;
    while(bfs()) 
    ret+=dfs(S,inf);
    return ret;
}
int main()
{
    cin>>m>>n;S=0;T=n+1;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++) scanf("%d",&w[i]);
    for(int a,x,b,i=1;i<=n;i++)
    {
        scanf("%d",&a);
        for(int j=1;j<=a;j++)
        {
            scanf("%d",&x);
            v[x].push_back(i);
        }
        scanf("%d",&b);
        add(i,T,b);
    }
    for(int i=1;i<=m;i++)
    if(v[i].size())
    {
        add(S,v[i][0],w[i]);
        for(int j=1;j<v[i].size();j++)
        add(v[i][j-1],v[i][j],inf);
    }
    cout<<dinic();
}```