今天学了一个炒鸡厉害的算法（听说是高端的图论时我们都自觉膜拜了好多次）二分图匹配；通过增广路发现了一件事：两个人都出轨的话，就多了一对情侣诶（呃！（还可以改进匹配诶）
参考资料：
1.不知道哪来的PPT；
2.小蓝；
基础概念：
1.二分图：设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图.(并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B) )
2.启发性：由一个方法可以自己借鉴解决其他许多问题；
一.完美的牛栏 poj1274
题意：二分完美匹配，n,m,<=200;
题目分析：这是一道很显然的二分图匹配，作用就是检测了我的理解（因为我的习惯是不看模板）
#include#include #include #include #include #include #include #include #include using namespace std;int n,m,ovo[205][205],match[205],visited[205],cnt,mini,maxn,s,c;bool hungary(int k){ for(int i=1;i<=maxn;i++) if(!visited[i]&&ovo[k][i]) { visited[i]=1; if(match[i]==-1||hungary(match[i]))//我可以搞定！match[i]说道。 { //快一点变过来变过来~ match[i]=k;return true;//从maxn记向mini； } } return false;}int main(){ freopen("milk.in","r",stdin); freopen("milk.out","w",stdout); while(scanf("%d %d",&n,&m)==2)//cow,fence//poj多组数据坑爹啊 {memset(ovo,0,sizeof(ovo));cnt=0;//初始化一定要撤点！ for(int i=1;i<=n;i++) { scanf("%d",&s); for(int j=1;j<=s;j++) { scanf("%d",&c); ovo[i][c]=1; } } mini=min(n,m);maxn=max(n,m); memset(match,-1,sizeof(match)); for(int i=1;i<=mini;i++) { memset(visited,0,sizeof(visited));//match是上次的地图君不清零！ if(hungary(i))cnt++; } printf("%d\n",cnt); } return 0;}
visited找一次广增只每个点都最多经历一次；
for1-n 最多增加n个
cnt++每次只多一个
match不置0；