2011-0040

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

= 题目大意 =
有N个小孩，每个小孩知道若干条信息，现在所有小孩要向大家分享最少Bi条最多Ci条信息，问编号为k的小孩最多能获知多少条信息。

= 解题报告 =
这题表示被坑了= =……原本以为是上下界网络流，搞半天才发现下界一点用都没有。注意到题目中有一句话，'''一条消息可以被不同的小孩分享多次'''，于是在一个最大解的情况下即使有小孩没有分享完下界，他随便挑几条分享都不会影响题目的结果，于是下界就被去除了。
于是题目就变成了一个比较简单的网络流模型，图左边放N个小孩，右边放若干条信息，每个小孩向信息连一条边，流量随便即可，源点向小孩连一条流量是他共享消息数目的上界，每条消息向汇点连一条流量为1的下界，然后网络流即可。注意到询问的K号小孩自己的消息是肯定知道的，所以将源点连向K号小孩的边特殊处理一下设置成无限大，这样就可以保证K号小孩知道自己的全部消息，该题解决。

= 题目代码 =
{{{
#include<cstdio>
#include<cstring>
#include<map>
#define MAXN 10005
#define oo 999999999

using namespace std;

int S,E,n,m,i,j,totxx,x,bh;
map<int,int> DY;
struct ChiType{
    int a,b,c,d[15];
}Chi[MAXN];

struct Dinic{
    struct EdgeType{
        int x,y,c;
        EdgeType *next,*back;
    }Edge[MAXN*20],*Gr[MAXN],*Cur[MAXN];
    int lv[MAXN],e,head,tail,que[MAXN*10],x,path[MAXN],p,i,min,mink,ans,k;

    int addedge(int x,int y,int c){
        Edge[++e].x=x;
        Edge[e].y=y;
        Edge[e].c=c;
        Edge[e].next=Gr[x];
        Gr[x]=&Edge[e];
        Edge[e].back=&Edge[e+1];
        Edge[++e].x=y;
        Edge[e].y=x;
        Edge[e].c=0;
        Edge[e].next=Gr[y];
        Gr[y]=&Edge[e];
        Edge[e].back=&Edge[e-1];
        return 0;
    }

    int clear(){
        e=0;
        memset(Gr,0,sizeof(Gr));
        memset(path,0,sizeof(path));
        memset(Edge,0,sizeof(Edge));
        return 0;
    }

    int find(){
        memset(que,0,sizeof(que));
        head=0; tail=1; que[tail]=S;
        memset(lv,255,sizeof(lv));
        lv[S]=0;
        do{
            head++;
            x=que[head];
            for(EdgeType *t=Gr[x];t;t=t->next){
                if(lv[t->y]==-1&&t->c>0){
                    tail++;
                    que[tail]=t->y;
                    lv[t->y]=lv[x]+1;
                    if(t->y==E)return 1;
                }
            }
        }while(head<=tail);
        return 0;
    }

    int flow(){
        ans=0;
        while(find()){
            path[0]=0; p=0;
            for(i=S;i<=E;i++)
                Cur[i]=Gr[i];
            do{
                x=path[p];
                if(x==E){
                    min=oo;
                    for(i=0;i<=p-1;i++)
                        if(Cur[path[i]]->c<min){
                            min=Cur[path[i]]->c;
                            mink=i;
                        }
                    ans+=min;
                    for(i=0;i<=p-1;i++){
                        Cur[path[i]]->c-=min;
                        Cur[path[i]]->back->c+=min;
                    }
                    p=mink; continue;
                }

                for(;Cur[x];Cur[x]=Cur[x]->next){
                    k=Cur[x]->y;
                    if(Cur[x]->c>0&&lv[x]+1==lv[k]){
                        path[++p]=k;
                        break;
                    }
                }
                if(!Cur[x]){
                    p--;
                    lv[x]=-1;
                }
            }while(p!=-1);
        }
        return ans;
    }
}Network;

int main(){
    while(scanf("%d",&n)!=EOF){
        Network.clear();
        DY.clear();
        for(i=1;i<=n;i++){
            scanf("%d%d%d",&Chi[i].a,&Chi[i].b,&Chi[i].c);
            for(j=1;j<=Chi[i].a;j++){
                scanf("%d",&x);
                if (DY.find(x)==DY.end()){
                    totxx++;
                    DY[x]=totxx;
                    bh=totxx;
                }else bh=DY[x];
                Chi[i].d[j]=bh;
            }
        }
        scanf("%d",&m);
        S=0; E=n+totxx+1;
        for(i=1;i<=n;i++){
            if(i==m)Network.addedge(S,i,oo);
            else Network.addedge(S,i,Chi[i].c);
            for(j=1;j<=Chi[i].a;j++)
                Network.addedge(i,Chi[i].d[j]+n,oo);
        }
        for(i=1;i<=totxx;i++)
            Network.addedge(i+n,E,1);
        printf("%d\n",Network.flow());
    }
}
}}}

Finished by Dai@NeverLand

题目大意

有N个小孩，每个小孩知道若干条信息，现在所有小孩要向大家分享最少Bi条最多Ci条信息，问编号为k的小孩最多能获知多少条信息。

解题报告

这题表示被坑了= =……原本以为是上下界网络流，搞半天才发现下界一点用都没有。注意到题目中有一句话，一条消息可以被不同的小孩分享多次，于是在一个最大解的情况下即使有小孩没有分享完下界，他随便挑几条分享都不会影响题目的结果，于是下界就被去除了。

于是题目就变成了一个比较简单的网络流模型，图左边放N个小孩，右边放若干条信息，每个小孩向信息连一条边，流量随便即可，源点向小孩连一条流量是他共享消息数目的上界，每条消息向汇点连一条流量为1的下界，然后网络流即可。注意到询问的K号小孩自己的消息是肯定知道的，所以将源点连向K号小孩的边特殊处理一下设置成无限大，这样就可以保证K号小孩知道自己的全部消息，该题解决。

题目代码

#include<cstdio>
#include<cstring>
#include<map>
#define MAXN 10005
#define oo 999999999
using namespace std;
int S,E,n,m,i,j,totxx,x,bh;
map<int,int> DY;
struct ChiType{
    int a,b,c,d[15];
}Chi[MAXN];
struct Dinic{
    struct EdgeType{
        int x,y,c;
        EdgeType *next,*back;
    }Edge[MAXN*20],*Gr[MAXN],*Cur[MAXN];
    int lv[MAXN],e,head,tail,que[MAXN*10],x,path[MAXN],p,i,min,mink,ans,k;
    int addedge(int x,int y,int c){
        Edge[++e].x=x;
        Edge[e].y=y;
        Edge[e].c=c;
        Edge[e].next=Gr[x];
        Gr[x]=&Edge[e];
        Edge[e].back=&Edge[e+1];
        Edge[++e].x=y;
        Edge[e].y=x;
        Edge[e].c=0;
        Edge[e].next=Gr[y];
        Gr[y]=&Edge[e];
        Edge[e].back=&Edge[e-1];
        return 0;
    }
    int clear(){
        e=0;
        memset(Gr,0,sizeof(Gr));
        memset(path,0,sizeof(path));
        memset(Edge,0,sizeof(Edge));
        return 0;
    }
    int find(){
        memset(que,0,sizeof(que));
        head=0; tail=1; que[tail]=S;
        memset(lv,255,sizeof(lv));
        lv[S]=0;
        do{
            head++;
            x=que[head];
            for(EdgeType *t=Gr[x];t;t=t->next){
                if(lv[t->y]==-1&&t->c>0){
                    tail++;
                    que[tail]=t->y;
                    lv[t->y]=lv[x]+1;
                    if(t->y==E)return 1;
                }
            }
        }while(head<=tail);
        return 0;
    }
    int flow(){
        ans=0;
        while(find()){
            path[0]=0; p=0;
            for(i=S;i<=E;i++)
                Cur[i]=Gr[i];
            do{
                x=path[p];
                if(x==E){
                    min=oo;
                    for(i=0;i<=p-1;i++)
                        if(Cur[path[i]]->c<min){
                            min=Cur[path[i]]->c;
                            mink=i;
                        }
                    ans+=min;
                    for(i=0;i<=p-1;i++){
                        Cur[path[i]]->c-=min;
                        Cur[path[i]]->back->c+=min;
                    }
                    p=mink; continue;
                }
                for(;Cur[x];Cur[x]=Cur[x]->next){
                    k=Cur[x]->y;
                    if(Cur[x]->c>0&&lv[x]+1==lv[k]){
                        path[++p]=k;
                        break;
                    }
                }
                if(!Cur[x]){
                    p--;
                    lv[x]=-1;
                }
            }while(p!=-1);
        }
        return ans;
    }
}Network;
int main(){
    while(scanf("%d",&n)!=EOF){
        Network.clear();
        DY.clear();
        for(i=1;i<=n;i++){
            scanf("%d%d%d",&Chi[i].a,&Chi[i].b,&Chi[i].c);
            for(j=1;j<=Chi[i].a;j++){
                scanf("%d",&x);
                if (DY.find(x)==DY.end()){
                    totxx++;
                    DY[x]=totxx;
                    bh=totxx;
                }else bh=DY[x];
                Chi[i].d[j]=bh;
            }
        }
        scanf("%d",&m);
        S=0; E=n+totxx+1;
        for(i=1;i<=n;i++){
            if(i==m)Network.addedge(S,i,oo);
            else Network.addedge(S,i,Chi[i].c);
            for(j=1;j<=Chi[i].a;j++)
                Network.addedge(i,Chi[i].d[j]+n,oo);
        }
        for(i=1;i<=totxx;i++)
            Network.addedge(i+n,E,1);
        printf("%d\n",Network.flow());
    }
}

Finished by Dai@NeverLand