Poj Solution 1043

http://poj.org/problem?id=1043

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

struct criminal
{
       char name[21];
       int id;
}crim[20];

int cmp(void const * a,void const * b)                                                                                                     //按姓名升序排序
{
    return strcmp(((criminal *)a)->name,((criminal *)b)->name);
}

int Bipartite(bool decryp[][20],int n,int count)                                                                                           //二分图的匈牙利算法,decryp是原始数组,n是用户ID的个数,count是罪犯的个数(列数)
{
    int i,j,x,qs,qe,q[20],prev[20],ncount=0;                                                                                               //匹配的个数
    int vm1[20],vm2[20];
    for(i=0;i<n;i++)
       vm1[i]=-1;                                                                                                                          //vm1[i]表示在已经匹配的集合中,vm1[i]与i相连,vm1表示用户ID点
    for(i=0;i<count;i++)
       vm2[i]=-1;                                                                                                                          //vm2[i]表示在已经匹配的集合中,vm2[i]与i相连,vm2便是name点
    for(i=0;i<n;i++)
    {
        for(j=0;j<count;j++)
          prev[j]=-2;
        qs=qe=0;
        for(j=0;j<count;j++)
         if(decryp[i][j])                                                                                                                 //与i可能匹配的点
         {
             prev[j]=-1;
             q[qe++]=j;                                                                                                                   //与i有关联的点进入队列q中
         }
        while(qs<qe)                                                                                                                      //寻找一条以i为起点的增广路径
        {
             x=q[qs];
             if(vm2[x]==-1)                                                                                                               //如果找到一个未匹配的点,即有一条增广路径,则进入下一步操作
                break;
             qs++;
             for(j=0;j<count;j++)
              if(prev[j]==-2&&decryp[vm2[x]][j])                                                                                          //如果j还未进入队列,即j=-1,并且vm2[x]到j有路径,则把j放入队列
              {
                  prev[j]=x;
                  q[qe++]=j;
              }
        }
        if(qs==qe)                                                                                                                        //如果没有找到则进行下一步操作
           continue;
        while(prev[x]>-1)                                                                                                                 //如果找到了,进行取反操作
        {
            vm1[vm2[prev[x]]]=x;
            vm2[x]=vm2[prev[x]];                                                                                                          //匹配的点交换,实现取反
            x=prev[x];
        }
        vm2[x]=i;                                                                                                                         //一个连接
        vm1[i]=x;
        ncount++;                                                                                                                         //匹配数加1
    }
    return ncount;
}

int main()
{
    int i,j,n,count;
    bool stay[20];                                                                                                                       //标记罪犯逗留在隐匿处
    bool decryp[20][20];                                                                                                                 //用于二分图计算的原始矩阵
    char op,str[21],buffer[30],id[20][21];
    scanf("%d",&n);
    for(i=0;i<n;i++)
      scanf("%s",id[i]);
    count=0;
    memset(decryp,true,sizeof(decryp));
    memset(stay,false,sizeof(stay));
    gets(buffer);                                                                                                                       //读取上一行数据的回车
    while(gets(buffer)&&buffer[0]!='Q')
    {
         sscanf(buffer,"%c %s",&op,str);
         if(op=='E')                                                                                                                    //罪犯藏于隐匿处
         {
             for(i=0;i<count&&strcmp(crim[i].name,str);i++);                                                                            //查找该罪犯是不是新来的
             if(i==count)                                                                                                               //该罪犯不是新来的
             {
                 strcpy(crim[count].name,str);
                 count++;                                                                                                               //计数
             }
             stay[i]=true;                                                                                                              //逗留在隐匿处
         }
         else if(op=='L')                                                                                                               //罪犯离开隐匿处
         {
              for(i=0;i<count&&strcmp(crim[i].name,str);i++);
              stay[i]=false;                                                                                                            //离开隐匿处
         }
         else                                                                                                                           //拦截到信息
         {
             for(i=0;i<n&&strcmp(id[i],str);i++);                                                                                       //查找用户ID的编号
             for(j=0;j<n;j++)                                                                                                           //所有呆在隐匿处的都有可能
               if(!stay[j])
                 decryp[i][j]=false;
         }
    }
    for(i=0;i<count;i++)                                                                                                                //查找罪犯姓名与用户ID之间的对应关系
    {
         crim[i].id=-1;                                                                                                                 //查找每个罪犯,初值为-1
         for(j=0;j<n&&crim[i].id==-1;j++)
         {
             if(decryp[j][i])                                                                                                           //表示i和j有匹配的可能
             {
                 decryp[j][i]=false;                                                                                                    //假设i和j不匹配
                 if(Bipartite(decryp,n,count)<count)                                                                        //调用匈牙利算法,若匹配数少于人数,则说明i和j必须匹配,否则不符合题意
                    crim[i].id=j;
                 decryp[j][i]=true;                                                                                                     //匹配后要还原
             }
         }
    }
    qsort(crim,count,sizeof(criminal),cmp);                                                                                             //按罪犯的姓名排序
    for(i=0;i<n;i++)
    {
         printf("%s:",crim[i].name);
         if(crim[i].id==-1)
            printf("???");
         else
            printf("%s",id[crim[i].id]);
         printf("n");
    }
    system("pause");
    return 0;
}