二分圖匹配

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <string> #include <fstream> #include <list> #include <stack> #include <queue> #include <deque> #include <algorithm> #include <map> #include <set> #include <vector> using namespace std; #define maxn 202 #define maxm 202 bool graph[maxn][maxm]; bool vis[maxm], flag; int match[maxn]; int N, M; bool find(int x) {int j;for (j = 0; j < M; j++){if (graph[x][j] == true && vis[j] == false){vis[j] = true;if (match[j] == -1 || find(match[j])){match[j] = x;return true;}}}return false; } int main() {//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios::sync_with_stdio(false);//cin.tie(0); cout.tie(0);//ifstream in;//in.open("input.txt", ios::in);scanf("%d%d", &N, &M);int t, s;for (int i = 0; i < N; ++i){scanf("%d", &t);for (int j = 0; j < t; ++j){scanf("%d", &s);--s;graph[i][s] = true;}}memset(match, -1, sizeof(int)*maxn);int ans = 0;for (int i = 0; i < N; ++i){memset(vis, 0, sizeof(vis));if (find(i))++ans;}printf("%d\n", ans);//while (1);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CDOJ 1144 Big Brother 二分图匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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