开发笔记:P1640[SCOI2010]连续攻击游戏

做了这么长时间的二分图, 终于发现一个只能用Hungary做的题了.

一眼二分图, 但是建模非常巧妙. 一开始的想法无非就是把两个属性当做二分图的两边, 但是发现这样似乎不好处理选其中一个的情况.

其实这个应该把属性放到左边, 编号放到右边匹配就ok.

因为编号必须连续的缘故, dinic此处就无能为力了,,,无奈的去现学了一下Hungary,,,

#include
#include
#include
#include
#include <iostream>
#include
using namespace std;
const int MAXN = 1e6 + 10;
inline int read(){
char ch = getchar(); int x = 0;
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - &＃39;0&＃39;, ch = getchar();
return x;
}
int N;
int match[MAXN]; bool vis[MAXN];
vector g[(int) 1e4 + 10];
bool dfs(int u) {
for(int i = 0; i <(int) g[u].size(); i++) {
int &v = g[u][i];
if(!vis[v]) {
vis[v] = true;
if(!match[v] || dfs(match[v])) return match[v] = u, true;
}
}
return false;
}
int main(){
cin>>N;
for(int i = 1; i <= N; i++)
g[read()].push_back(i), g[read()].push_back(i);
int ans = 0;
for(int i = 1; i <= (int) 1e4; i++) {
memset(vis, false, (N + 1) * sizeof(bool));
if(dfs(i)) ++ans; else break;
}
printf("%d
", ans);
return 0;
}