題目
Description
“那么真的有果爾德施坦因這樣一個人?”他問道。
“是啊，有這樣一個人，他還活著。至于在哪里，我就不知道了。”
“那么那個密謀——那個組織?這是真的嗎?不是秘密警察的捏造吧?”
“不是，這是真的。我們管它叫兄弟會。除了它確實存在，你們是它的會員以外，你們 就別想知道別的了。”
他知道的是，這種思想一定會一代一代地傳下去，他們一定能夠在沒有黑暗的地方再會。
他不知道的是，兄弟會已經走到了崩潰的邊緣；思想警察早已無孔不入；那沒有黑暗的地方， 是友愛部，是 101 室……
兄弟會的頭目之一，愛麥虞埃爾?果爾德施坦因，正在謀劃著一場無力的反抗。這抗爭的內容，竟是一場宏大的舞會。（這作為小資情調、腐朽沒落的代表，以及未經允許的群眾運動， 是大洋國嚴格禁止的（甚至是 crimethink））這也是為了加強組織的團結，并且為那終將到來的最后一戰而激勵、鼓舞士氣。
眾所周知，兄弟會為了避免思想警察的追捕，保密措施相當嚴密。會內一位高級干部奧勃良如此說：“從你們切身經驗來說，你們永遠連十來個會員也不認識。”（注意：測試數據可能不符合這句話）具體來說，每個人只認識他的全部上司。一個人的上司要么是他的直接上司
（在輸入中會向你給出，并且可能不止一人），要么是這個人的某個上司的直接上司。為了增進同志之間的感情，同時為了防止滲入兄弟會的間諜破獲整個組織的組成與結構，果爾德 施坦因想要確保在舞會中任意兩個人都互不相識。
真理部的外圍黨員溫斯頓在奧勃良的介紹下加入了兄弟會。他剛剛知道了這個激動人心的舞 會，仿佛又感受到了那若有若無的、來自舊時代的溫暖。因為參與舞會的人越多，他與他親愛的裘莉亞就越有可能重逢，所以他很好奇最多能有多少人參與。Input
第一行兩個正整數 N，M，表示兄弟會的會員人數以及關系數。然后 M 行，每行 2 個正整數 x,y（1<=x,y<=N,x≠y），表示 x 是 y 的直接上司（即 y 是 x 的直接下屬）。
Output
輸出一行一個整數，表示參加舞會的最多人數。
Sample Input
4 4
1 2
2 4
1 3
3 4Sample Output
2
Data Constraint
對于 5%數據，滿足 n<=5。
對于 20%數據，滿足 n<=20。
對于另 10%數據，滿足會員構成一棵外向樹，即：除了一號會員（即果爾德施坦因本人）之外的每個會員，恰好只有一個上司，且一號會員沒有上司。
對于另 10%數據，滿足會員構成一顆內向樹，即：除了一號會員（即溫斯頓）之外的每個會員，恰好只有一個直接下屬，且一號會員沒有下屬。
對于另 30%數據，滿足每個會員要么沒有上司，要么沒有下屬。
對于 100%數據，滿足 n<=200，關系不會重復出現，且不會自相矛盾（即 A 既是 B 的上司也是 B 的下屬）。換句話說，關系構成了一張無重邊的有向無環圖。保證圖聯通。
做法
顯然，這是一個有向無環圖。
對于每一條有向邊(u,v)(u,v)，表示vv是uu的的上司。
題目要讓我們在圖上找到盡量多的點，使得這些點不能互相到達。
咋做？
題解上這樣說：
在有向無環圖中，我們定義：
鏈：圖上一些點的集合，對于鏈上任意兩個點 x、y，滿足 x 能到達 y 或者 y
能到達 x。
反鏈：圖上一些點的的集合，對于反鏈上任意兩個點 x、y，滿足 x 不能到達
y 并且 y 不能到達 x。
所以就是很顯然的求最長反鏈長度了~
有以下 Dilworth 定理：
最長反鏈長度=最小鏈覆蓋（選取最少的鏈覆蓋所有的點）
這是題解上話，然后我上網找這條定理的證明，結果……證明很少，并且好幾篇博客是一個樣子，而且讓我一臉懵逼，甚至感覺那證明還是錯的……
于是，只能感性理解。
假設用一些鏈來覆蓋整張圖。
對于每個反鏈上的點，它們各自在一條鏈上。
如果這些鏈的數量大于最小鏈覆蓋，那么多出來的那些都是廢的，會出現兩個反鏈上的點能連通，與題目不符……
好吧，感性理解這種東西是不方便用語言來說的。
現在假設我們已經知道了這個定理。
接下來可以用二分圖匹配來解決：
將每個點拆成左右兩邊（實現時不需要）。
對于一條邊(u,v)(u,v)，就在二分圖上uleftuleft和vrightvright連一條有向邊。
跑一遍二分圖匹配，那么答案就是n?最大匹配數n?最大匹配數。
Why?
在二分圖，連一條邊，可以視為將兩條鏈合并，也就是將最小鏈覆蓋數?1?1。
拆成二分圖，避免路徑相交的問題。
代碼
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 200
int n,m;
bool to[MAXN+1][MAXN+1];//表示是否連通
int be[MAXN*2+1];
bool vis[MAXN+1];
bool matching(int);
int main(){freopen("dance.in","r",stdin);freopen("dance.out","w",stdout);scanf("%d%d",&n,&m);for (int i=1;i<=m;++i){int u,v;scanf("%d%d",&u,&v);to[v][u]=1;}//要用Floyed來處理處連通性for (int k=1;k<=n;++k)for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)to[i][j]|=to[i][k]&&to[k][j]; int max_matching=0;for (int i=1;i<=n;++i){memset(vis,0,sizeof vis);if (matching(i))max_matching++;}printf("%d\n",n-max_matching);return 0;
}
bool matching(int x){for (int i=1;i<=n;++i)if (to[x][i] && !vis[i]){vis[i]=1;if (!be[i] || matching(be[i])){be[i]=x;return 1;}}return 0;
}總結
這題好打是好打，就是理解得迷迷糊糊的。
感性理解還是很重要的……
