Strategic Game
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8503 Accepted Submission(s): 4093
Problem Description
Your program should find the minimum number of soldiers that Bob has to put for a given tree.
The input file contains several data sets in text format. Each data set represents a tree with the following description:
the number of nodes
the description of each node in the following format
node_identifier:(number_of_roads) node_identifier1 node_identifier2 ... node_identifier
or
node_identifier:(0)
The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.
For example for the tree:
the solution is one soldier ( at the node 1).
The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table:
Sample Input
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)
Sample Output
2
Source
//2017-08-26
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int N = ;
const int M = ;
int head[N], tot;
struct Edge{
int to, next;
}edge[M]; void init(){
tot = ;
memset(head, -, sizeof(head));
} void add_edge(int u, int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++; edge[tot].to = u;
edge[tot].next = head[v];
head[v] = tot++;
} int n;
int matching[N];
int check[N]; bool dfs(int u){
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].to;
if(!check[v]){//要求不在交替路
check[v] = ;//放入交替路
if(matching[v] == - || dfs(matching[v])){
//如果是未匹配点，说明交替路为增广路，则交换路径，并返回成功
matching[u] = v;
matching[v] = u;
return true;
}
}
}
return false;//不存在增广路
} //hungarian: 二分图最大匹配匈牙利算法
//input: null
//output: ans 最大匹配数
int hungarian(){
int ans = ;
memset(matching, -, sizeof(matching));
for(int u = ; u < n; u++){
if(matching[u] == -){
memset(check, , sizeof(check));
if(dfs(u))
ans++;
}
}
return ans;
} int main()
{
std::ios::sync_with_stdio(false);
//freopen("inputH.txt", "r", stdin);
string str;
while(cin>>n){
init();
int u, k, v;
for(int i = ; i < n; i++){
cin>>str;
u = , k = ;
int ptr = ;
while(str[ptr] != ':'){
u *= ;
u += str[ptr]-'';
ptr++;
}
ptr+=;
while(str[ptr] != ')'){
k *= ;
k += str[ptr]-'';
ptr++;
}
for(int j = ; j < k; j++){
cin>>v;
add_edge(u, n+v);
add_edge(v, n+u);
}
}
cout<<hungarian()/<<endl;
} return ;
}