hdu 6073 Matching In Multiplication(拓撲排序+歐拉回路)

題目連結：hdu 6073 Matching In Multiplication

題意：

給你2*n個點，左邊n個點每個點都有兩條邊，求所有完美比對的邊權乘積的和，題目保證至少有一個完美比對。

題解：

首先我們先找出各個連通塊，每個連通塊隻要度不是為1的話肯定都是為2的。

是以就先用拓撲排序将度為1的點對處理掉，這些點對隻有一種選擇，然後剩下的就是度為2的連通塊。

随便從一個點開始走，沿着邊走，肯定能回到起點，這就是一個歐拉回路。

将走的這些邊編号，編号為奇數的為一組，編号為偶數的為一組，這兩組就是這個連通塊的兩種比對方式。

然後将每個連通塊的答案都乘起來就行了。

1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 
 5 const int N=6e5+7,P=998244353;
 6 int t,n,ed,g[N],v[N*2],nxt[N*2],w[N*2],vis[N*2];
 7 int cnt,in[N],ans,Q[N],hd,tl;
 8 
 9 void adg(int x,int y,int z){in[y]++,v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}
10 
11 inline int go(int x){
12     for(int i=g[x];i;i=nxt[i])
13         if(!vis[v[i]])return v[i];
14     return 0;
15 }
16 inline int get(int x,int y){for(int i=g[x];i;i=nxt[i])if(v[i]==y)return w[i];}
17 
18 int main(){
19     scanf("%d",&t);
20     while(t--)
21     {
22         ed=0,cnt=0,ans=1,hd=1,tl=0,scanf("%d",&n);
23         F(i,1,n<<1)g[i]=0,in[i]=0,vis[i]=0;
24         int a,b,c,d;
25         F(i,1,n)
26         {
27             scanf("%d%d%d%d",&a,&b,&c,&d);
28             adg(i,a+n,b),adg(n+a,i,b);
29             adg(i,c+n,d),adg(c+n,i,d);
30         }
31         F(i,n+1,n<<1)if(in[i]==1)Q[++tl]=i;
32         while(hd<=tl)
33         {
34             int x=Q[hd++],y;
35             for(int i=g[x];i;i=nxt[i])if(!vis[v[i]])
36                 y=v[i],ans=1ll*ans*w[i]%P;
37             vis[x]=vis[y]=1;
38             for(int i=g[y];i;i=nxt[i])if(!vis[v[i]])
39                 if(--in[v[i]]==1)Q[++tl]=v[i];
40         }
41         int an[2];
42         F(i,1,n)if(!vis[i])
43         {
44             Q[tl=1]=i,vis[i]=1;
45             for(int j=go(i);j;j=go(j))vis[Q[++tl]=j]=1;
46             Q[tl+1]=i,an[0]=an[1]=1;
47             F(j,1,tl)an[j&1]=1ll*an[j&1]*get(Q[j],Q[j+1])%P;
48             ans=1ll*ans*(an[0]+an[1])%P;
49         }
50         printf("%d\n",ans);
51     }
52     return 0;
53 }      

View Code

轉載于:https://www.cnblogs.com/bin-gege/p/7281918.html