信与信封问题

时间限制: 1 s

空间限制: 128000 KB

题目描述 Description

John先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。

将Small John所提供的n封信依次编号为1，2，…，n；且n个信封也依次编号为1，2，…，n。假定Small John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装回信封。

输入描述 Input Description

n文件的第一行是一个整数n（n≤100）。信和信封依次编号为1，2，…，n。

n接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。文件最后一行是2个0，表示结束。

输出描述 Output Description

输出文件的各行中每行有2个数i和j，表示第i封信肯定是装在第j个信封中。请按信的编号i从小到大顺序输出。若不能确定正确装入信封的任何信件，则输出“none”。

样例输入 Sample Input

1 2

1 3

2 1

0 0

样例输出 Sample Output

1 1

题目链接：http://codevs.cn/problem/1222/

思路是二分图匹配。不过不太好写，首先要对信可能放在哪些信封里建边，然后跑二分图匹配，如果匹配数不等于n，则直接就是none，然后依次枚举每封信，看看它在残留网络中与哪个信封之间有一条流量，就能知道这封信是放在了哪里，然后把这条边断掉，再跑一次二分图匹配，如果还能跑完美匹配，说明这封信有多个去处，则不输出它，否则说明这封信只能放在断掉边的信封里，则输出它。

#include<bits/stdc++.h>
#define N 205
using namespace std;

typedef struct
{
    int to,next;
    long long flow;
}ss;

ss edg[N*N];
int now_edge=0,s,t;
int head[N];

int num_edge[N][N]={0};

void addedge(int u,int v,long long flow)
{
    edg[now_edge]=(ss){v,head[u],flow};
    num_edge[u][v]=head[u]=now_edge++;
    
    edg[now_edge]=(ss){u,head[v],0};
    num_edge[v][u]=head[v]=now_edge++;
}

int dis[N];

bool bfs()
{
    memset(dis,0,sizeof(dis));
    queue<int>q;
    q.push(s);
    dis[s]=1;
    
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i!=-1;i=edg[i].next)
        {
            ss &e=edg[i];
            if(e.flow>0&&dis[e.to]==0)
            {
                dis[e.to]=dis[now]+1;
                q.push(e.to);
            }
        }
    }
    
    if(dis[t]==0)return 0;
    return 1;
}

int current[N];
long long dfs(int x,long long maxflow)
{
    if(x==t)return maxflow;
//    printf("%d %lld
",x,maxflow);
    for(int i=current[x];i!=-1;i=edg[i].next)
    {
        current[x]=i;
        ss &e=edg[i];
        if(e.flow>0&&dis[e.to]==dis[x]+1)
        {
            long long flow=dfs(e.to,min(maxflow,e.flow));
            if(flow!=0)
            {
                e.flow-=flow;
                edg[i^1].flow+=flow;
                return flow;
            }
        }
    }
    return 0;
}

long long dinic()
{
    long long ans=0,flow;
    while(bfs())
    {
        for(int i=0;i<N;i++)current[i]=head[i];
        while(flow=dfs(s,LLONG_MAX/2))ans+=flow;
    }
    return ans;
}

void init()
{
    for(int i=0;i<N;i++)head[i]=-1;
    now_edge=0;
}

int Map[N][N]={0};

int main()
{
    int n;
    init();
    scanf("%d",&n);
    int a,b;
    while(scanf("%d %d",&a,&b)==2)
    {
        if(!a)break;
        Map[a][b]=1;
    }

    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(!Map[i][j])
    {
        addedge(i,j+n,1);
    }
    s=2*n+1;
    t=2*n+2;

    for(int i=1;i<=n;i++)addedge(s,i,1),addedge(i+n,t,1);
    
    long long now=dinic();
    
    if(now!=n){printf("none
");return 0;}
    
    int tot=0,used_edge;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j!=-1;j=edg[j].next)
        {
            if(edg[j].to!=s&&edg[j^1].flow)
            {
             used_edge=j;
            // printf("%d
",j);
             break;
            }
        }
        
        ss &e=edg[used_edge];
        edg[num_edge[i][s]].flow=0;
        edg[num_edge[s][i]].flow=1;
        edg[num_edge[e.to][t]].flow=1;
        edg[num_edge[t][e.to]].flow=0;
        edg[used_edge^1].flow=0;
        
        int tt=dinic();
    //    printf("%d
",tt);
        if(tt==0)
        {
            tot++;
            printf("%d %d
",i,edg[used_edge].to-n);
            
            edg[num_edge[i][s]].flow=1;
            edg[num_edge[s][i]].flow=0;
            edg[num_edge[e.to][t]].flow=0;
            edg[num_edge[t][e.to]].flow=1;
            edg[used_edge^1].flow=1;
        }
        else
        e.flow=1;
    }
    
    if(!tot)printf("none
");
    return 0;
}

View Code