HDU 6073 Matching In Multiplication（拓扑排序+思维）

http://acm.hdu.edu.cn/showproblem.php?pid=6073

题意：
有个二分图，左边和右边的顶点数相同，左边的顶点每个顶点度数为2。现在有个屌丝理解错了最佳完美匹配，它以为最佳完美匹配是边权的乘积了，现在要你计算所有这种最佳完美匹配的边权乘积和。保证至少存在一个完美匹配。

思路：

这道题目虽然打着二分图的幌子，但其实吧，根本就不是二分图，哎。

对于右边的点来说，如果它的度数为1，那么与它匹配的点肯定是确定的，所以我们先通过拓扑排序来计算出所有确定的匹配。去除这些点后，假设左边和右边各还剩下x个点，此时还有2x条边，此时右边顶点每个顶点的度数必为2。

此时其实就是连通图，对于左边的每一个顶点，它都有两种边可供选择，然而一旦确定了一条边之后，整个环就都确定下来了，所以对于一个环来说共有两种选择方法。

参考了大神的dfs方法，太强了！！！

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef pair<int,int> pll;
 15 const int INF = 0x3f3f3f3f;
 16 const int maxn=3e5+5;
 17 const int mod=998244353;
 18 
 19 int n;
 20 int tot, head[2*maxn];
 21 int del[2*maxn], deg[maxn];
 22 ll res[3];
 23 
 24 struct node
 25 {
 26     int v, w, next;
 27     int mark;
 28 }e[4*maxn];
 29 
 30 void addEdge(int u, int v, int w)
 31 {
 32     e[tot].v=v; e[tot].w=w; e[tot].next=head[u]; e[tot].mark=0;
 33     head[u]=tot++;
 34 }
 35 
 36 void init()
 37 {
 38     tot=0;
 39     memset(head,-1,sizeof(head));
 40     memset(deg,0,sizeof(deg));
 41     memset(del,0,sizeof(del));
 42 }
 43 
 44 void dfs(int u, int flag)
 45 {
 46     del[u]=1;
 47     for(int i=head[u];i!=-1;i=e[i].next)
 48     {
 49         if(e[i].mark)  continue;
 50         int v=e[i].v;
 51         e[i].mark=e[i^1].mark=1;
 52         res[flag]=(res[flag]*e[i].w)%mod;
 53         dfs(v,flag^1);
 54     }
 55 }
 56 
 57 int main()
 58 {
 59     //freopen("in.txt","r",stdin);
 60     int T;
 61     scanf("%d",&T);
 62     while(T--)
 63     {
 64         init();
 65         scanf("%d",&n);
 66         for(int i=1;i<=n;i++)
 67         {
 68             int v1,d1,v2,d2;
 69             scanf("%d%d%d%d",&v1,&d1,&v2,&d2);
 70             addEdge(i,v1+n,d1); addEdge(v1+n,i,d1);
 71             addEdge(i,v2+n,d2); addEdge(v2+n,i,d2);
 72             deg[v1]++; deg[v2]++;
 73         }
 74 
 75         ll ans=1;
 76         queue<int> Q;
 77         for(int i=1;i<=n;i++)
 78             if(deg[i]==1)  Q.push(i+n);
 79 
 80         while(!Q.empty())
 81         {
 82             int u=Q.front(); Q.pop();
 83             del[u]=1;
 84             for(int i=head[u];i!=-1;i=e[i].next)  //左边
 85             {
 86                 if(e[i].mark)  continue;
 87                 int v=e[i].v;
 88                 del[v]=1;
 89                 e[i].mark=e[i^1].mark=1;
 90                 ans=(ans*e[i].w)%mod;
 91 
 92                 for(int j=head[v];j!=-1;j=e[j].next)  //右边
 93                 {
 94                     if(e[j].mark)  continue;
 95                     int p=e[j].v;
 96                     deg[p-n]--;
 97                     e[j].mark=e[j^1].mark=1;
 98                     if(deg[p-n]==1)  Q.push(p);
 99                 }
100             }
101         }
102 
103         for(int i=1;i<=n;i++)
104         {
105             if(!del[i])
106             {
107                 res[0]=res[1]=1;
108                 dfs(i,0);
109                 ans=(ans*((res[0]%mod+res[1]%mod)%mod))%mod;
110             }
111         }
112         printf("%I64d
",ans);
113     }
114     return 0;
115 }

HDU 6073 Matching In Multiplication（拓扑排序+思维）

相关推荐