匈牙利算法..從1~10000依次找增廣路, 找不到就停止, 輸出答案.?
----------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
const int MAXL = 10009, MAXR = 1000009;
struct edge {
int to;
edge* next;
} E[MAXR << 1], *pt = E, *head[MAXL];
inline void addedge(int u, int v) {
pt->to = v; pt->next = head[u];
head[u] = pt++;
}
int match[MAXR], vis[MAXR], N, C;
bool dfs(int x) {
for(edge* e = head[x]; e; e = e->next) if(vis[e->to] != C) {
vis[e->to] = C;
if(!~match[e->to] || dfs(match[e->to])) {
? ?match[e->to] = x;
return true;
}
}
return false;
}
int main() {
memset(match, -1, sizeof match);
memset(vis, -1, sizeof vis);
scanf("%d", &N);
for(int i = 0; i < N; i++) {
int a, b; scanf("%d%d", &a, &b); a--; b--;
addedge(a, i); addedge(b, i);
}
int ans = 0;
for(C = 0; C < 10000; C++) {
if(dfs(C)) ans++;
else break;
}
printf("%d\n", ans);
return 0;
}
----------------------------------------------------------------------------?
1854: [Scoi2010]游戲
Time Limit:?5 Sec??Memory Limit:?162 MBSubmit:?3022??Solved:?1100
[Submit][Status][Discuss]
Description
lxhgww最近迷上了一款游戲，在游戲里，他擁有很多的裝備，每種裝備都有2個屬性，這些屬性的值用[1,10000]之間的數表示。當他使用某種裝備時，他只能使用該裝備的某一個屬性。并且每種裝備最多只能使用一次。 游戲進行到最后，lxhgww遇到了終極boss，這個終極boss很奇怪，攻擊他的裝備所使用的屬性值必須從1開始連續遞增地攻擊，才能對boss產生傷害。也就是說一開始的時候，lxhgww只能使用某個屬性值為1的裝備攻擊boss，然后只能使用某個屬性值為2的裝備攻擊boss，然后只能使用某個屬性值為3的裝備攻擊boss……以此類推。 現在lxhgww想知道他最多能連續攻擊boss多少次？
Input
輸入的第一行是一個整數N，表示lxhgww擁有N種裝備 接下來N行，是對這N種裝備的描述，每行2個數字，表示第i種裝備的2個屬性值
Output
輸出一行，包括1個數字，表示lxhgww最多能連續攻擊的次數。
Sample Input
3
1 2
3 2
4 5
1 2
3 2
4 5
Sample Output
2
HINT
【數據范圍】
對于30%的數據，保證N < =1000
對于100%的數據，保證N < =1000000
Source
Day1
?
)
