HDU - 1845 Jimmy’s Assignment (二分匹配)
HDU 匹配 二分 assignment
2023-09-27 14:27:21 时间
Description
Jimmy is studying Advanced Graph Algorithms at his university. His most recent assignment is to find a maximum matching in a special kind of graph. This graph is undirected, has N vertices and each vertex has degree 3. Furthermore,
the graph is 2-edge-connected (that is, at least 2 edges need to be removed in order to make the graph disconnected). A matching is a subset of the graph’s edges, such that no two edges in the subset have a common vertex. A maximum matching is a matching having
the maximum cardinality.
Given a series of instances of the special graph mentioned above, find the cardinality of a maximum matching for each instance.
Given a series of instances of the special graph mentioned above, find the cardinality of a maximum matching for each instance.
Input
The first line of input contains an integer number T, representing the number of graph descriptions to follow. Each description contains on the first line an even integer number N (4<=N<=5000), representing the number of vertices.
Each of the next 3*N/2 lines contains two integers A and B, separated by one blank, denoting that there is an edge between vertex A and vertex B. The vertices are numbered from 1 to N. No edge may appear twice in the input.
Output
For each of the T graphs, in the order given in the input, print one line containing the cardinality of a maximum matching.
Sample Input
2
4
1 2
1 3
1 4
2 3
2 4
3 4
4
1 2
1 3
1 4
2 3
2 4
3 4
Sample Output
2
2
Source
Politehnica University of Bucharest Local Team Contest 2007
题意:给你双向边,求最多留下多少条边使得每条边都没有共同拥有顶点
思路:二分图匹配的定义。对于双向的要/2。用vector会超时。要用邻接表
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 5010;
const int MAXM = 50010;
struct Edge {
int to, next;
} edge[MAXM];
int head[MAXN], tot;
int linker[MAXN];
bool used[MAXN];
int n, m;
void init() {
tot = 0;
memset(head,-1,sizeof(head));
}
void addEdge(int u, int v) {
edge[tot].to = v; edge[tot].next = head[u];
head[u] = tot++;
}
bool dfs(int u) {
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (!used[v]) {
used[v] = true;
if (linker[v] == -1 || dfs(linker[v])) {
linker[v] = u;
return true;
}
}
}
return false;
}
int solve() {
int ans = 0;
memset(linker, -1, sizeof(linker));
for (int i = 0; i < n; i++) {
memset(used, false, sizeof(used));
if (dfs(i))
ans++;
}
return ans;
}
int main() {
int t;
scanf("%d",&t);
while (t--) {
scanf("%d", &n);
m = n*3/2;
int u,v;
init();
while (m--) {
scanf("%d%d", &u, &v);
u--; v--;
addEdge(u,v);
addEdge(v,u);
}
printf("%d\n", solve()/2);
}
return 0;
}
相关文章
- 致初学者(四):HDU 2044~2050 递推专项习题解
- hdu 5400 Arithmetic Sequence
- 【HDU 2063】过山车(二分图最大匹配模板题)
- hdu 1102 Constructing Roads(kruskal || prim)
- HDU 1253 胜利大逃亡 NYOJ 523【BFS】
- HDU 2883 kebab
- HDU 3915 Game (高斯消元)
- HDU 1207 汉诺塔II (简单DP)
- HDU 5912 Fraction (模拟)
- HDU 1272 小希的迷宫 (并查集)
- 【HDU 1150】Machine Schedule(二分图匹配)
- HDU 5297 Y sequence Y数列
- hdu 4035 可能性DP 成都网络游戏
- hdu 2444 The Accomodation of Students (判断二分图,最大匹配)