首页 > 代码库 > POJ 1149 网络流 合并建图

POJ 1149 网络流 合并建图

2024-07-02 22:00:46   227人阅读

这个题目我敲了一个简单的EK，这不是难点

难点在于建图，按题目的要求 每个猪圈和顾客都建点的话，那也太多了。。。我看了Edelweiss里面的缩点方法才建好的图，哎，惭愧啊

实际那些猪圈根本不需要单独建点，猪圈无非就是向顾客输送流量 以及向同时开着的猪圈输送流量，这一步可以直接缩为，当某个猪圈被第一次打开，它里面的流量就全部输送给那个顾客那个点，而且可以叠加，因为每一次猪圈是可以互通的，而且猪圈本身是没有容量限制，如果有限制，那就还得再考虑。

此外，每次对猪圈的接下来的访问者都进行建边。用来输送之后的流量

处理好初始点和结束点。

#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 1<<30
using namespace std;
int m,n;
int pigs[1010],cap[110][110],f[110][110],vis[1010][110],buys;
int inq[1010],cnt[1010];
void init(){
    memset(cap,0,sizeof cap);
    memset(f,0,sizeof cap);
    memset(vis,0,sizeof vis);
    memset(inq,0,sizeof inq);
    memset(cnt,0,sizeof cnt);
}
int ans,q[110],a[110],p[110];
void ek()
{
    ans=0;
    const int M=105;
    for (;;){
        memset(a,0,sizeof a);
        int head,rear;
        head=rear=0;
        a[0]=INF;
        q[rear++]=0;
        while(head!=rear){
            int u=q[head++];
            if (head>=M) head%=M;
            for (int v=0;v<=n+1;v++) if (!a[v] && cap[u][v]>f[u][v]){
                p[v]=u;
                q[rear++]=v;
                if (rear>=M) rear%=M;
                a[v]=min(a[u],cap[u][v]-f[u][v]);
            }
        }
        if (a[n+1]==0) break;
        for (int u=n+1;u!=0;u=p[u]){
            f[p[u]][u]+=a[n+1];
            f[u][p[u]]-=a[n+1];
        }
        ans+=a[n+1];
    }
}

int main()
{
    while (scanf("%d%d",&m,&n)!=EOF)
    {
        init();
        int tmp,a;
        for (int i=1;i<=m;i++) scanf("%d",&pigs[i]);
        for (int i=1;i<=n;i++){
            scanf("%d",&tmp);
            for (int j=0;j<tmp;j++){
                scanf("%d",&a);
                vis[a][cnt[a]++]=i;
                if (inq[a]) continue;
                inq[a]=1;
                cap[0][i]+=pigs[a];
            }
            scanf("%d",&buys);
            cap[i][n+1]=buys;
        }
        for (int i=1;i<=m;i++){
            for (int j=0;j<cnt[i]-1;j++){
                    int a=vis[i][j];
                    int b=vis[i][j+1];
                    cap[a][b]=INF;
                }
        }
   }
        ek();
        printf("%d\n",ans);
    }
    return 0;
}

 


联系
我们