UVALive-3268 Jamie's Contact Groups （最大流，网络流建模）

题目大意：你的手机通讯录里有n个联系人，m个分组，其中，有的联系人在多个分组里。你的任务是在一些分组里删除一些联系人，使得每个联系人只在一个分组里并且使人数最多的那个分组人数最少。找出人数最多的那个分组中的人数。

题目分析：要求的是最小的最大值，二分枚举这个最小的最大人数x。增加源点s和汇点t，从s向每一个联系人连一条弧，容量为1，表示一个联系人只能在一个分组中；然后对于每个联系人向他所在的分组连一条弧，容量为1，表示在这个分组里最多保存一次该联系人；然后从每个分组向汇点连一条弧，容量为x，表示这个分组不能保存超过x个联系人。求最大流，如果源点s出发的每条边都满载，说明x可行。

代码如下：

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

struct Edge
{
    int fr,to,cap,fw;
    Edge(int _fr,int _to,int _cap,int _fw):fr(_fr),to(_to),cap(_cap),fw(_fw){}
};
vector<Edge>edges,tedges;
vector<int>G[N];
int cur[N],vis[N],d[N],mark[505];

void init(int n)
{
    edges.clear();
    REP(i,0,n) G[i].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 m=edges.size();
    G[u].push_back(m-2);
    G[v].push_back(m-1);
}

bool BFS(int s,int t)
{
    CL(vis,0);
    vis[s]=1;
    d[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        REP(i,0,G[u].size()){
            Edge &e=edges[G[u][i]];
            if(!vis[e.to]&&e.cap>e.fw){
                d[e.to]=d[u]+1;
                vis[e.to]=1;
                q.push(e.to);
            }
        }
    }
    return vis[t];
}

int DFS(int u,int t,int a)
{
    if(u==t||a==0) return a;
    int flow=0,f;
    for(int &i=cur[u];i<G[u].size();++i){
        Edge &e=edges[G[u][i]];
        if(d[e.to]==d[u]+1&&(f=DFS(e.to,t,min(a,e.cap-e.fw)))>0){
            e.fw+=f;
            edges[G[u][i]^1].fw-=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}

int Dinic(int s,int t)
{
    int flow=0;
    while(BFS(s,t)){
        CL(cur,0);
        flow+=DFS(s,t,INF);
    }
    return flow;
}

bool read(int &x)
{
    x=0;
    char c;
    while(c=getchar()){
        if(c==' ') return true;
        else if(c=='
') return false;
        else x=x*10+c-'0';
    }
}

bool judge()
{
    REP(i,0,G[0].size())
        if(edges[G[0][i]].cap>0&&edges[G[0][i]].cap!=edges[G[0][i]].fw) return false;
    return true;
}

int main()
{
    int n,m;
    char name[20];
    while(scanf("%d%d",&n,&m)&&(n+m))
    {
        init(n+m+2);
        CL(mark,0);
        REP(i,1,n+1){
            cin>>name;
            addEdge(0,m+i,1);
            int a;
            getchar();
            while(read(a)){
                ++mark[a];
                addEdge(m+i,a+1,1);
            }
            addEdge(m+i,a+1,1);
            ++mark[a];
        }

        int cnt=edges.size();
        tedges.clear();
        REP(i,0,cnt) tedges.push_back(edges[i]);

        int l=0,r=0;
        REP(i,0,m) r=max(r,mark[i]);
        while(l<r){
            int mid=l+(r-l)/2;
            init(n+m+2);
            REP(i,0,cnt) addEdge(tedges[i].fr,tedges[i].to,tedges[i].cap);
            REP(i,0,m) if(mark[i])
                addEdge(i+1,n+m+1,min(mid,mark[i]));
            Dinic(0,n+m+1);
            if(judge()) r=mid;
            else l=mid+1;
        }
        printf("%d
",l);
    }
    return 0;
}

UVALive-3268 Jamie's Contact Groups （最大流，网络流建模）

相关推荐