文章目錄

• 題目描述
• 解析
• 解析

題目描述

在遙遠的東方，有一個神秘的民族，自稱Y族。他們世代居住在水面上，奉龍王為神。每逢重大慶典， Y族都會在水面上舉辦盛大的祭祀活動。我們可以把Y族居住地水系看成一個由岔口和河道組成的網絡。每條河道連接著兩個岔口，并且水在河道內按照一個固定的方向流動。顯然，水系中不會有環流
由于人數眾多的原因，Y族的祭祀活動會在多個岔口上同時舉行。出于對龍王的尊重，這些祭祀地點的選擇必須非常慎重。準確地說，Y族人認為，如果水流可以從一個祭祀點流到另外一個祭祀點，那么祭祀就會失去它神圣的意義。族長希望在保持祭祀神圣性的基礎上，選擇盡可能多的祭祀的地點。

解析

有一說一本題第二問的方案構造我沒有完全理解
首先考慮我們利用類似弗洛伊德的方法，求出這個DAG的傳遞閉包，這樣問題就轉化成了在圖中找到最大獨立集
考慮把一個點割成入點和出點，這樣本題就變成了二分圖最大獨立集，直接n-最大匹配即可
然后就是第二問，考慮構造出這個最大獨立集
考慮一種方法：

從右邊未匹配的點開始dfs，右邊走非匹配邊，左邊只走匹配邊
只選取左邊dfs到的和右邊沒被dfs到的點

考慮所有情況的邊都會被覆蓋到，所有這樣就可以構造出一個最小點覆蓋
然后我們取補集就是一個最大獨立集

第三問，我們只需要強制選該點，把這個點和相關點刪去，然后嘗試再跑一邊匈牙利看是否只與答案差一即可

解析

#include<bits/stdc++.h> using namespace std; const int N=305; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m,l; struct node{int from,to,nxt; }p[N*N*4]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){x,y,fi[x]};fi[x]=cnt; } int vis[N],mat[N],num,op[N]; bool dfs(int x,int tim){if(vis[x]==tim) return false;vis[x]=tim;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(!mat[to]||dfs(mat[to],tim)){mat[to]=x;return true;}}return false; } int hungary(){int res=0;memset(vis,0,sizeof(vis));memset(mat,0,sizeof(mat));for(int i=1;i<=n;i++){if(dfs(i,i)){res++;//printf(" ok:%d\n",i);}}return res; } bool mp[105][105]; bool jd[N]; void find(int x){if(jd[x]) return;jd[x]=1;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;jd[to]=1;find(mat[to]);} } int main(){memset(fi,-1,sizeof(fi));n=read();m=read();for(int i=1;i<=m;i++){int x=read(),y=read();mp[x][y]=1;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) mp[i][j]|= (mp[i][k]&&mp[k][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j]) addline(i+n,j),addline(j,i+n);}}int res=hungary();printf("%d\n",n-res);for(int i=n+1;i<=2*n;i++){mat[mat[i]]=i;}for(int i=n+1;i<=2*n;i++){if(!mat[i]) find(i);}for(int i=1;i<=n;i++){if(!jd[i]&&jd[i+n]) printf("1");else printf("0");}printf("\n");for(int i=1;i<=n;i++){//printf("i=%d-----\n",i);memset(fi,-1,sizeof(fi));cnt=-1;int tot=0;for(int j=1;j<=n;j++){if(j==i||mp[i][j]||mp[j][i]) op[j]=1;else{op[j]=0;tot++;}}for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){if(!op[j]&&!op[k]&&mp[j][k]){//printf("%d->%d\n",j,k);addline(j,k+n);}}}int o=hungary();//printf("tot=%d res=%d\n",tot,o);printf("%d",tot-o+1==n-res);}return 0; } /* 4 4 1 2 3 4 3 2 4 21010 1011 */

總結

以上是生活随笔為你收集整理的YBTOJ洛谷P4298：祭祀（二分图匹配）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。