poj 1904(强连通分量+完美匹配)

传送门:Problem 1904

https://www.cnblogs.com/violet-acmer/p/9739990.html

参考资料：

　　[1]:http://www.cnblogs.com/frog112111/p/3384261.html

　　[2]:https://blog.csdn.net/a709743744/article/details/52133778

　　[3]:http://www.cppblog.com/Uriel/articles/121169.html

题意：

　　有n个王子，每个王子都有k个喜欢的妹子，每个王子只能和喜欢的妹子结婚，大臣给出一个匹配表，每个王子都和一个妹子结婚，但是国王不满意，他要求大臣给他另一个表，每个王子可以和几个妹子结婚，按序号升序输出妹子的编号，这个表应满足所有的王子最终都有妹子和他结婚。

分析：

　　很好的图论题，把强连通分量和完美匹配结合起来了。

　　2*N 个顶点的2 分图，并且给了一个完美匹配(Perfect Matching)以及每个顶点可以连接的其他的顶点。

　　题目要求是否可以确定某 2 个顶点连边后，其他 2*(N - 1) 个顶点的 2 分图是否可以构成完美匹配。

建图：

　　如果王子u喜欢妹子v，则建一条边u指向v(u,v)，对于大臣给出的初始完美匹配，如果王子u和妹子v结婚，则建一条边v指向u(v,u)，然后求强连通分量。

　　对于每个王子和妹子，如果他们都在同一个强连通分量内，则他们可以结婚。

　　为什么呢？因为每个王子只能和喜欢的妹子结婚，初始完美匹配中的丈夫和妻子之间有两条方向不同的边可以互达，则同一个强连通分量中的王子数和妹子数一定是相等的，若王子 x 可以和另外的一个妹子 a 结婚，妹子 a 的原配王子 y 肯定能找到另外一个妹子 b 结婚，因为如果找不到的话，则 x 和 a 必不在同一个强连通分量中。

所以一个王子可以和所有与他同一强连通分量的妹子结婚，而这不会导致同一强连通分量中的其他王子找不到妹子结婚。

　　（证明：王子为什么不能选择不同强连通分量的妹子：

　　反证法：如果强连通分量 1 中的王子选择了强连通分量 2 中的妹子,那么势必强连通分量 2 中的一个王子无法在自己的强连通分量中找到妹子,那么他就会去别的强连通分量找妹子,这样一直循环下去，我们知道最终一定是经过了强连通分量 1,2,x1,x2,xn,……,1，王子们才能都找到自己的妹子，这样这些强连通分量1,2,x1,x2,xn,……,1会构成一个强连通分量,与题设在不同强连通分量中找妹子不符）

此题难点：建图

AC代码：

这一题的数据量挺大的，光是输入输出就会消耗很多时间了，可以用输入输出外挂来加速读入和输出。

Kosaraju算法：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 #define mem(a,b) memset(a,b,sizeof a)
 8 #define pb push_back
 9 const int maxV=4e3+50;
10 
11 int scc[maxV];
12 bool vis[maxV];
13 vector<int >vs;
14 vector<int >edge[maxV],redge[maxV];
15 
16 void addEdge(int u,int v)
17 {
18     edge[u].pb(v);
19     redge[v].pb(u);
20 }
21 void Dfs(int u)
22 {
23     vis[u]=true;
24     for(int i=0;i < edge[u].size();++i)
25     {
26         int to=edge[u][i];
27         if(!vis[to])
28             Dfs(to);
29     }
30     vs.pb(u);
31 }
32 void rDfs(int u,int sccId)
33 {
34     scc[u]=sccId;
35     vis[u]=true;
36     for(int i=0;i < redge[u].size();++i)
37     {
38         int to=redge[u][i];
39         if(!vis[to])
40             rDfs(to,sccId);
41     }
42 }
43 void Scc(int maxV)
44 {
45     mem(vis,false);
46     vs.clear();
47     for(int i=1;i <= maxV;++i)
48         if(!vis[i])
49             Dfs(i);
50     mem(vis,false);
51     int sccId=0;
52     for(int i=vs.size()-1;i >= 0;--i)
53     {
54         int v=vs[i];
55         if(!vis[v])
56         {
57             sccId++;
58             rDfs(v,sccId);
59         }
60     }
61 }
62 int main()
63 {
64     int N;
65     scanf("%d",&N);
66     for(int i=1;i <= N;++i)
67     {
68         int k,v;
69         scanf("%d",&k);
70         while(k--)
71         {
72             scanf("%d",&v);
73             addEdge(i,v+N);//王子i喜欢妹子v
74         }
75     }
76     for(int i=1;i <= N;++i)
77     {
78         int v;
79         scanf("%d",&v);
80         addEdge(v+N,i);//王子i可以和妹子v结婚
81     }
82     Scc(N);
83     for(int i=1;i <= N;++i)
84     {
85         int res=0;
86         int ans[maxV];
87         for(int j=0;j < edge[i].size();++j)
88         {
89             int to=edge[i][j];
90             if(scc[i] == scc[to])//同一个强连通分量
91                 ans[res++]=to;
92         }
93         sort(ans,ans+res);
94         printf("%d",res);
95         for(int j=0;j < res;++j)
96             printf(" %d",ans[j]-N);
97         printf("
");
98     }
99 }

不用输入输出挂

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<vector>
  4 #include<cstring>
  5 #include<algorithm>
  6 using namespace std;
  7 #define mem(a,b) memset(a,b,sizeof a)
  8 #define pb push_back
  9 const int maxV=4e3+50;
 10 
 11 int scc[maxV];
 12 bool vis[maxV];
 13 vector<int >vs;
 14 vector<int >edge[maxV],redge[maxV];
 15 
 16 void addEdge(int u,int v)
 17 {
 18     edge[u].pb(v);
 19     redge[v].pb(u);
 20 }
 21 void Dfs(int u)
 22 {
 23     vis[u]=true;
 24     for(int i=0;i < edge[u].size();++i)
 25     {
 26         int to=edge[u][i];
 27         if(!vis[to])
 28             Dfs(to);
 29     }
 30     vs.pb(u);
 31 }
 32 void rDfs(int u,int sccId)
 33 {
 34     scc[u]=sccId;
 35     vis[u]=true;
 36     for(int i=0;i < redge[u].size();++i)
 37     {
 38         int to=redge[u][i];
 39         if(!vis[to])
 40             rDfs(to,sccId);
 41     }
 42 }
 43 void Scc(int maxV)
 44 {
 45     mem(vis,false);
 46     vs.clear();
 47     for(int i=1;i <= maxV;++i)
 48         if(!vis[i])
 49             Dfs(i);
 50     mem(vis,false);
 51     int sccId=0;
 52     for(int i=vs.size()-1;i >= 0;--i)
 53     {
 54         int v=vs[i];
 55         if(!vis[v])
 56         {
 57             sccId++;
 58             rDfs(v,sccId);
 59         }
 60     }
 61 }
 62 //===============输入输出挂===============
 63 int Scan()     //输入外挂
 64 {
 65     int res=0,ch,flag=0;
 66     if((ch=getchar())=='-')
 67         flag=1;
 68     else if(ch>='0'&&ch<='9')
 69         res=ch-'0';
 70     while((ch=getchar())>='0'&&ch<='9')
 71         res=res*10+ch-'0';
 72 
 73     return flag?-res:res;
 74 }
 75 void Out(int a)    //输出外挂
 76 {
 77     if(a>9)
 78         Out(a/10);
 79     putchar(a%10+'0');
 80 }
 81 //========================================
 82 int main()
 83 {
 84     int N;
 85     scanf("%d",&N);
 86     for(int i=1;i <= N;++i)
 87     {
 88         int k,v;
 89         //scanf("%d",&k);
 90         k=Scan();
 91         while(k--)
 92         {
 93             //scanf("%d",&v);
 94             v=Scan();
 95             addEdge(i,v+N);//王子i喜欢妹子v
 96         }
 97     }
 98     for(int i=1;i <= N;++i)
 99     {
100         int v;
101         //scanf("%d",&v);
102         v=Scan();
103         addEdge(v+N,i);//王子i可以和妹子v结婚
104     }
105     Scc(N);
106     for(int i=1;i <= N;++i)
107     {
108         int res=0;
109         int ans[maxV];
110         for(int j=0;j < edge[i].size();++j)
111         {
112             int to=edge[i][j];
113             if(scc[i] == scc[to])//同一个强连通分量
114                 ans[res++]=to;
115         }
116         sort(ans,ans+res);
117         //printf("%d",res);
118         Out(res);
119         for(int j=0;j < res;++j)
120         {
121             printf(" ");
122             Out(ans[j]-N);
123             //printf(" %d",ans[j]-N);
124         }
125         printf("
");
126     }
127 }

调用输入输出挂

好晚了，身心疲惫，明天在补Tarjan算法...............