Gym - 100741F（二分匹配 矩阵斜线线与值进行匹配）

题目链接：https://vjudge.net/contest/181019#problem/F

题意：给定一个n*n的矩阵，从左下至右上平行于对角线的斜线共2*n-1条（包括对角线），在每条斜线上选取一个出现的值，要求这2*n-1条斜线选取的值互不相同，求是否能选取，若不能，输出NO，若能，输出YES并按1~2*n-1的顺序输出每条斜线上选取的值。

思路：从左下至右上为这些斜线编号为1~2*n-1，将编号x与斜线x上出现的数值进行连线，求出最大匹配数是否为2*n-1即可。注意数值较大，可以为每个数赋一个较小的id值放置vis数组越界。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<sstream>
#include<deque>
#include<stack>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const int
maxn = 1000 + 20;
const int
maxt = 300 + 10;
const int mod = 10;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int Dis[] = {-1, 1, -5, 5};
const int inf = 0x3f3f3f3f;
const int MOD = 1000;
int n, m, k;
int d[maxn][maxn];
int match[100000 + 10];//因match数组开小WA一次
bool vis[100000 + 10];//因vis数组开太小RE一次
vector<int> g[maxn];
map<int, int> id;
map<int, int> pos;
int ans[maxn];
bool dfs(int u){
int v;
int len = g[u].size();
for(int i = 0; i < len; ++i){
v = g[u][i];
if(vis[v]) continue;
vis[v] = true;
if(match[v] == -1 || dfs(match[v])){
match[v] = u;
ans[u] = v;//记录每条斜线的当前匹配值
return true;
}
}
return false;
}
int main(){
scanf("%d", &n);
int xx = 610;
id.clear(); pos.clear();
memset(d, 0, sizeof d);
for(int i = 0; i < maxn; ++i) g[i].clear();
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
scanf("%d",&d[i][j]);
if(id.find(d[i][j]) == id.end()){//d[i][j]的值太大，根据输入顺序为其编号，防止RE
id[d[i][j]] = xx;
pos[xx++] = d[i][j];
}
}
}
int t = n;
int num = 1, x = 2 * n;
while(t >= 1){//遍历每一条斜线，从左下至右上id编号依次为1~2*n-1，将斜线上存在的数值id值与斜线id值连线
for(int i = t, j = 1; i <= n; ++i,++j){
if(t != 1){
g[num].push_back(id[d[i][j]]);
g[x - num].push_back(id[d[j][i]]);
}
else{
g[num].push_back(id[d[i][j]]);
}
}
++num; --t;
}
int cnt = 0;
bool ok = true;
memset(ans, 0, sizeof ans);
memset(match, -1, sizeof match);
for(int i = 1; i < x; ++i){//为每一条斜线寻找匹配值
memset(vis, false, sizeof vis);
if(dfs(i)){
++cnt;
}
else{//若有某条斜线无匹配值，直接退出
ok = false; break;
}
}
if(!ok || cnt != 2 * n - 1){
printf("NOn"); return 0;
}
printf("YES");
for(int i = 1; i < x; ++i){
printf(" %d", pos[ans[i]]);
}
printf("n");
return 0;
}
/*
5
1000000000 1000000000 1000000000 900000000 210000000
1000000000 200000000 200000000 800000000 700000000
1000000000 200000000 300000000 300000000 700000000
1000000000 200000000 600000000 400000000 700000000
700000000
700000000
700000000 00000000
700000000
//1 2 6 4 3 8 9
4
1 1 1 9
1 2 2 8
1 2 4 4
1 2 6 5
5
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
3
1 1 1
2 2 4
3 1 1
*/

最后

以上就是危机月亮为你收集整理的Gym - 100741F（二分匹配 矩阵斜线线与值进行匹配）的全部内容，希望文章能够帮你解决Gym - 100741F（二分匹配 矩阵斜线线与值进行匹配）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。