书海扬帆的博客

短小精悍的一个算法,提出者是匈牙利著名数学家Edmonds.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn=1010;
bool flag[maxn][maxn],vis[maxn];
int match[maxn];
int m,n,e,ans;
inline bool dfs(int cur){
for(int i=1;i<=m;i++){
if(flag[cur][i] && !vis[i]){
vis[i]=1;
if(!match[i] || dfs(match[i])){
match[i]=cur;
return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&e);
for(int i=1;i<=e;i++){
int a,b;
scanf("%d%d",&a,&b);
if(a<=n && b<=m) flag[a][b]=true;
}
for(int i=1;i<=n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i)) ans++;
}
printf("%d\n",ans);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;

const int maxn=10010;
int a[maxn],l[maxn],t[maxn],n;
inline int turn(int x,int y) {
//变换得到的距离
return min(abs(x-y),n-abs(x-y));
}
vector<int> G[maxn];
bool vis[maxn];
inline bool find(int x) {
int v;
for(int i=0;i<G[i].size();i++) {
if(!vis[G[x][i]]) {
vis[G[x][i]]=1;
if(l[G[x][i]]==0||find(l[G[x][i]])) {
l[G[x][i]]=x;
return true;
}
}
}
return false;
}
int main() {
scanf("%d",&n);
//加边
for(int i=0;i<n;i++) {
scanf("%d",&a[i]);
int u=i+a[i],v=n+i-a[i];
u%=n;
v%=n;
if(turn(u,i)!=a[i]) u=-3625;
if(turn(v,i)!=a[i]) v=-3625;
if(u>v) swap(u,v);
if(u!=-3625) G[i].push_back(u);
if(v!=-3625) G[i].push_back(v);
}
for(int i=n-1;i>=0;i--) {
memset(vis,0,sizeof(vis));
if(!find(i)) {
printf("No Answer");
return 0;
}
}
for(int i=0;i<n;i++) t[l[i]]=i;
for(int i=0;i<n;i++) printf("%d ",t[i]);
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k