Poj_1325 Machine Schedule -最大匹配性质题目

题目：用最少的起点，带上所有的边

分析：对于最大匹配，其中一半的点可以连上所有的边。可以反面去证明，若存在一条边最大匹配中的匹配点都不与它相连，那么加入这条边，并不会破坏匹配的性质并且使最大匹配大一，与假设矛盾，所以证明成立。

/************************************************ Author :DarkTong Created Time :2016/7/31 11:28:07 File Name :Poj_1325.cpp *************************************************///#include <bits/stdc++.h> #include <cstdio> #include <cstring> using namespace std; const int maxn = 300 + 10; int w[maxn][maxn], n, m; int Left[maxn]; bool used[maxn]; bool match(int i) {for(int j=1;j<=n;++j) if(w[j][i]&&!used[j]){used[j] = true;if(!Left[j]||match(Left[j])){Left[j] = i;return true;}}return false; } //返回最大匹配数 int hungary() {int res=0;memset(Left, 0, sizeof(Left));for(int i=1;i<=m;++i){memset(used, 0, sizeof(used));if(match(i)) res++;}return res; }int main() {int T, cas=1;int k;while(scanf("%d", &n)==1&&n){scanf("%d%d", &m, &k);memset(w, 0, sizeof(w));int a, b, c;for(int i=0;i<k;++i){scanf("%d%d%d", &a, &b, &c);w[b][c]=1;}printf("%d\n", hungary());}return 0; }

转载于:https://www.cnblogs.com/DarkTong/p/5722692.html

总结

以上是生活随笔为你收集整理的Poj_1325 Machine Schedule -最大匹配性质题目的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。