題目：用最少的起點(diǎn)，帶上所有的邊

分析：對(duì)于最大匹配，其中一半的點(diǎn)可以連上所有的邊。可以反面去證明，若存在一條邊最大匹配中的匹配點(diǎn)都不與它相連，那么加入這條邊，并不會(huì)破壞匹配的性質(zhì)并且使最大匹配大一，與假設(shè)矛盾，所以證明成立。

/************************************************ 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; } //返回最大匹配數(shù) 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; }

轉(zhuǎn)載于:https://www.cnblogs.com/DarkTong/p/5722692.html

總結(jié)

以上是生活随笔為你收集整理的Poj_1325 Machine Schedule -最大匹配性质题目的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。