社区讨论

AC但是仍然有一些疑惑

eeXquisite_crYstalZ
P14581[LNCPC 2025] 海鸥奇遇参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mjfoeid6
此快照首次捕获于
2025/12/21 20:00
3 个月前
此快照最后确认于
2025/12/24 16:00
2 个月前
查看原帖
我的写法就是官方题解的Bonus里提到的写法，感性理解应该是每次消除环的过程一定会减少边的数量，那直接选择能让边数量最少的选择应该会更优。但是有点奇怪的是让海鸥去匹配食物并且按照距离排序就不能通过，并且我也构造出了反例，是匈牙利算法把本来最优的解法给改成不优了，所以想知道这两种做法的本质区别在哪里，为什么一个能过一个过不了qwq
反例（B=Bird，F=Food）：
CPP
FBBBBBBBF
 FFFFF
如果最右边B的先选会去选到最右边的F，然后这时候第二靠右的B再选也会想去吃右边的F，就把最右边的B赶去吃左边的了。
两种做法的代码如下
AC：
CPP
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 5010;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const char opid[4] = {'U', 'D', 'L', 'R'};

int T;
int n;
pair<char, int> a[N][N];
struct Bird{ int x, y; } b[N];
struct Food{ int x, y; } f[N];
struct Edge{
    int v;
    char op;
    vector<int> path;
    Edge(){ path.clear(); }
    bool operator< (const Edge &B) const {
        return path.size() < B.path.size();
    }
};
vector<Edge> G1[N];
vector<int> G2[N];
int match[N];
bool st[N];
int deg[N];
Edge ans[N];

bool in_range(int x, int y){
    return x >= 1 && x <= 5000 && y >= 1 && y <= 5000;
}

bool hungary(int u){
    for(Edge e : G1[u]){
        int v = e.v;
        if(st[v]) continue;
        st[v] = 1;
        if(!match[v] || hungary(match[v])){
            match[v] = u;
            ans[v] = e;
            return true;
        }
    }
    return false;
}

void solve(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &b[i].x, &b[i].y);
        a[b[i].x][b[i].y] = {'b', i};
    }
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &f[i].x, &f[i].y);
        a[f[i].x][f[i].y] = {'f', i};
    }
    for(int i = 1; i <= n; i++){
        G1[i].clear();
        G2[i].clear();
        match[i] = 0;
        deg[i] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int id = 0; id < 4; id++){
            int x = f[i].x, y = f[i].y;
            Edge e; e.op = opid[id];
            x += dx[id];
            y += dy[id];
            while(in_range(x, y) && a[x][y].first == 'b'){
                e.v = a[x][y].second;
                G1[i].push_back(e);
                e.path.push_back(a[x][y].second);
                x += dx[id];
                y += dy[id];
            }
        }
        sort(G1[i].begin(), G1[i].end());
    }
    int match_cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            st[j] = 0;
        if(hungary(i)) match_cnt++;
    }
    if(match_cnt == n){
        puts("Yes");
        for(int u = 1; u <= n; u++)
            for(int v : ans[u].path){
                if(u == v) continue;
                G2[u].push_back(v);
                deg[v]++;
            }
        queue<int> q;
        for(int i = 1; i <= n; i++)
            if(deg[i] == 0)
                q.push(i);
        while(q.size()){
            int u = q.front();
            q.pop();
            printf("%d %c\n", u, ans[u].op);
            for(int v : G2[u]){
                deg[v]--;
                if(deg[v] == 0) q.push(v);
            }
        }
    }else puts("No");
    for(int i = 1; i <= n; i++)
        a[b[i].x][b[i].y] = {0, 0};
    for(int i = 1; i <= n; i++)
        a[f[i].x][f[i].y] = {0, 0};
}

int main(){
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}
WA on #5：
CPP
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 5010;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const char opid[4] = {'U', 'D', 'L', 'R'};

int T;
int n;
pair<char, int> a[N][N];
struct Bird{ int x, y; } b[N];
struct Food{ int x, y; } f[N];
struct Edge{
    int v;
    char op;
    vector<int> path;
    Edge(){ path.clear(); }
    bool operator< (const Edge &B) const {
        return path.size() < B.path.size();
    }
};
vector<Edge> G1[N];
vector<int> G2[N];
int match[N];
bool st[N];
int deg[N];
Edge ans[N];

bool in_range(int x, int y){
    return x >= 1 && x <= 5000 && y >= 1 && y <= 5000;
}

bool hungary(int u){
    for(Edge e : G1[u]){
        int v = e.v;
        if(st[v]) continue;
        st[v] = 1;
        if(!match[v] || hungary(match[v])){
            match[v] = u;
            ans[u] = e;
            return true;
        }
    }
    return false;
}

void solve(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &b[i].x, &b[i].y);
        a[b[i].x][b[i].y] = {'b', i};
    }
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &f[i].x, &f[i].y);
        a[f[i].x][f[i].y] = {'f', i};
    }
    for(int i = 1; i <= n; i++){
        G1[i].clear();
        G2[i].clear();
        match[i] = 0;
        deg[i] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int id = 0; id < 4; id++){
            int x = b[i].x, y = b[i].y;
            Edge e; e.op = opid[id];
            while(in_range(x, y) && a[x][y].first == 'b'){
                e.path.push_back(a[x][y].second);
                x += dx[id];
                y += dy[id];
            }
            if(!in_range(x, y)) continue;
            if(a[x][y].first == 'f'){
                e.v = a[x][y].second;
                G1[i].push_back(e);
            }
        }
        sort(G1[i].begin(), G1[i].end());
    }
    int match_cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            st[j] = 0;
        if(hungary(i)) match_cnt++;
    }
    if(match_cnt == n){
        puts("Yes");
        for(int u = 1; u <= n; u++)
            for(int v : ans[u].path){
                if(u == v) continue;
                G2[u].push_back(v);
                deg[v]++;
            }
        queue<int> q;
        for(int i = 1; i <= n; i++)
            if(deg[i] == 0)
                q.push(i);
        while(q.size()){
            int u = q.front();
            q.pop();
            printf("%d %c\n", u, ans[u].op);
            for(int v : G2[u]){
                deg[v]--;
                if(deg[v] == 0) q.push(v);
            }
        }
    }else puts("No");
    for(int i = 1; i <= n; i++)
        a[b[i].x][b[i].y] = {0, 0};
    for(int i = 1; i <= n; i++)
        a[f[i].x][f[i].y] = {0, 0};
}

int main(){
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

回复

共 2 条回复，欢迎继续交流。

正在加载回复...