试题库问题（网络24题，五）

                                                                           试题库问题

题目链接：Click Here~

算法分析：

   只能用一个又字了。一道跟圆桌问题一样的属于二分多重匹配建图问题。在说一下多重匹配的概念吧；

假设一个有X集合和Y集合的一个二部图。  

多重匹配：就是X中的一个点可以与Y中的多个点匹配。X，Y相反当然也成立。

而这我们平时所说的二分匹配（除了多重匹配），稳定婚姻...一些二部图都是一个X集合中的点只能匹配一个有且仅有一个点的匹配方法。

   说会改题的解法吧，现在做最大流越来越有手感了。^_^ 其实还是一道考察建图能力的题，跟圆桌问题基本一样，就是把题目类型和题目题号分成X,Y集合。然后，从建图。一开始我是把题号建在了前面，结果写完要输出的时候发现输出的时候太麻烦了，于是就该变了建图的顺序。然后，就可以很好的输出题目的要求了。建完图后就可以用最大流求解多重匹配的解了。这是老生常谈了，不想再说。最后，判断最大流是否等于每个类型题目所需的总和。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 1e3 + 5;
const int INF = 1e8;
struct Edge{
   int from,to,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int s,t,d[maxn],cur[maxn],b[maxn];
bool vst[maxn];
void Init(int k,int n)
{
    s = 0,t = n+k+1;
    for(int i = 0;i < maxn;++i)
        G[i].clear();
    edges.clear();
}
void AddEdge(int from,int to,int cap)
{
    edges.push_back((Edge){from,to,cap,0});
    edges.push_back((Edge){to,from,0,0});
    int sz = edges.size();
    G[from].push_back(sz-2);
    G[to].push_back(sz-1);
}
bool BFS()
{
    memset(vst,false,sizeof(vst));
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    vst[s] = true;
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(int i = 0;i < (int)G[u].size();++i){
           Edge& e = edges[G[u][i]];
           if(!vst[e.to]&&e.cap > e.flow){
              vst[e.to] = true;
              d[e.to] = d[u]+1;
              Q.push(e.to);
           }
        }
    }
    return vst[t];
}
int DFS(int u,int a)
{
    if(u==t||a==0)
        return a;
    int f,flow = 0;
    for(int& i = cur[u];i < (int)G[u].size();++i){
        Edge& e = edges[G[u][i]];
        if(d[e.to]==d[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
            e.flow += f;
            edges[G[u][i]^1].flow -= f;
            flow += f;
            a -= f;
            if(a==0)break;
        }
    }
    return flow;
}
int Maxflow()
{
    int flow = 0;
    while(BFS()){
        memset(cur,0,sizeof(cur));
        flow += DFS(s,INF);
    }
    return flow;
}
void Print(int n,int k)
{
   for(int u = 1;u <= k;++u){
      printf("%d:",u);
      for(int i = 0;i < (int)G[u].size();++i){
          Edge& e = edges[G[u][i]];
          if(e.flow == 1&&e.from!=s&&e.to!=t)
            printf(" %d",e.to-k);
      }
      printf("\n");
   }
}
int main()
{
    int n,k;
    while(~scanf("%d%d",&k,&n))
    {
        Init(k,n);
        int num,x,sum = 0;
        for(int i = 1;i <= k;++i){
            scanf("%d",&b[i]);
            sum += b[i];
            AddEdge(s,i,b[i]);
        }
        for(int i = 1;i <= n;++i){
            scanf("%d",&num);
            AddEdge(i+k,t,num);
            while(num--){
                scanf("%d",&x);
                AddEdge(x,i+k,1);
            }
        }
        int flow = Maxflow();
        if(flow==sum)
            Print(n,k);
        else
            puts("No Solution!");
    }
    return 0;
}

试题库问题（网络24题，五）,布布扣,bubuko.com

试题库问题（网络24题，五）

原文：http://blog.csdn.net/zhongshijunacm/article/details/22674319