由於人數眾多的原因,Y族的祭祀活動會在多個岔口上同時舉行。出於對龍王的尊重,這些祭祀地點的選擇必 須非常慎重。准確地說,Y族人認為,如果水流可以從一個祭祀點流到另外一個祭祀點,那麼祭祀就會失去它神聖 的意義。族長希望在保持祭祀神聖性的基礎上,選擇盡可能多的祭祀的地點。
含兩個用空格隔開的整數u、v,描述一條連接岔口u和岔口v的河道,水流方向為自u向v。 N ≤ 100 M ≤ 1 000
第一行包含一個整數K,表示最多能選取的祭祀點的個數。
先floyd傳遞閉包,再求最小路徑覆蓋
常用定理:
最小點覆蓋=最大匹配。
最小邊覆蓋=最大獨立集=圖中點的個數-最大匹配。
最長反鏈=最小路徑覆蓋=原圖的節點數-新圖最大匹配。
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long #define N 210 inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,pp[N],dis[N],u,v,ans,tim; bool mp[N][N]; bool dfs(int x) { for(int i=1;i<=n;i++) if(mp[x][i]) { if(dis[i]==tim) continue; dis[i]=tim; if(!pp[i]||dfs(pp[i])){pp[i]=x;return 1;} } return 0; } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { u=read();v=read(); mp[u][v]=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]; ans=n; for(int i=1;i<=n;i++) tim++,ans-=dfs(i); printf("%d\n",ans); return 0; }