HDU 2444 The Accomodation of Students(dfs + 匈牙利算法)

题目大意:

解题思路:

先是要判断是否为二部图,然后求最大匹配。

#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <algorithm>using namespace std;const int MAXN = 200 +10;struct Edge{int to;int next;}edge[MAXN*MAXN];int n, m;int e;int head[MAXN];int vis[MAXN];int col[MAXN];int match[MAXN];void AddEdge(int u, int v){edge[e].to = v;edge[e].next = head[u];head[u] = e;e++;edge[e].to = u;edge[e].next = head[v];head[v] = e;e++;}bool dfs(int u, int pre){for(int i=head[u];i!=-1;i=edge[i].next){int v = edge[i].to;if(v == pre) continue;if(col[v] == -1){col[v] = col[u] ^ 1;dfs(v, u);}else if(col[v] == col[u])return false;}return true;}int path(int u){for(int i=head[u];i!=-1;i=edge[i].next){int v = edge[i].to;if(vis[v]) continue;vis[v] = 1;if(match[v] == -1 || path(match[v])){match[v] = u;return 1;}}return 0;}int main(){while(scanf("%d%d", &n, &m)!=EOF){memset(head, -1, sizeof(head));memset(match, -1, sizeof(match));memset(vis, 0, sizeof(vis));memset(col, -1, sizeof(col));e = 0;int u, v;for(int i=1;i<=m;i++){scanf("%d%d", &u, &v);AddEdge(u, v);}int ans = 0;col[1] = 1;if(!dfs(1, -1)){printf("No\n");continue;}else{for(int i=1;i<=n;i++){memset(vis, 0, sizeof(vis));if(path(i)) ans++;}printf("%d\n", ans / 2);}}return 0;}



,影子依旧可以相亲相爱。哪一块骨骼最温暖,总能一击即中。

HDU 2444 The Accomodation of Students(dfs + 匈牙利算法)

相关文章:

你感兴趣的文章:

标签云: