在我代码中随着我调整MAX_V的值会给出我不同的评分。当我的MAX_V为5e3+10的时候TLE了两个点,而当将这个值改为5e3+100的时候却莫名奇妙地过了,然而我其他什么代码也没有改。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
namespace Primal_Dual {
using ll = long long;
const int MAX_V = 5e3 + 100;
const ll INF = 1e12;
struct Edge {
int from, to;
ll cup, flow, cost;
Edge(int u, int v, ll c, ll f, ll w) : from(u), to(v), cup(c), flow(f), cost(w) {}
};
struct Graph {
int n, m, s, t;
vector<Edge> es;
vector<int> G[MAX_V];
ll dis[MAX_V], h[MAX_V];
int prevv[MAX_V], preve[MAX_V];
bool vis[MAX_V];
Graph(int s, int t, int n = MAX_V) : s(s), t(t), n(n) {
es.clear();
for(int i = 0; i < n; i ++) {
G[i].clear();
}
}
void add_Edge(int u, int v, ll cup, ll cost) {
es.push_back({u, v, cup, 0, cost}), es.push_back({v, u, 0, 0, -cost});
m = es.size();
G[u].push_back(m - 2), G[v].push_back({m - 1});
}
void spfa() {
queue<int> q;
for(int i = 0; i < n; i ++) {
h[i] = INF;
}
h[s] = 0, vis[s] = true;
q.push(s);
while(q.size()) {
int u = q.front();
q.pop();
vis[u] = false;
for(int i : G[u]) {
const Edge& e = es[i];
if(e.cup > e.flow && h[e.to] > h[e.from] + e.cost) {
h[e.to] = h[e.from] + e.cost;
if(!vis[e.to]) {
q.push(e.to);
vis[e.to] = true;
}
}
}
}
}
struct mypair {
ll dis;
int id;
bool operator< (const mypair& a) const {
return dis > a.dis;
}
};
bool Dij() {
for(int i = 0; i < n; i ++) {
dis[i] = INF;
}
memset(vis, 0, sizeof vis);
priority_queue<mypair> q;
dis[s] = 0;
q.push({dis[s], s});
while(q.size()) {
int u = q.top().id;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i : G[u]) {
const Edge& e = es[i];
ll nc = e.cost + h[e.from] - h[e.to];
if(e.cup > e.flow && dis[e.to] > dis[e.from] + nc) {
dis[e.to] = dis[e.from] + nc;
prevv[e.to] = e.from;
preve[e.to] = i;
q.push({dis[e.to], e.to});
}
}
}
return dis[t] < INF;
}
auto maxf_minc() {
spfa();
ll maxf = 0;
ll minc = 0;
while(Dij()) {
ll f = INF;
for(int i = 0; i < n; i ++) if(dis[i] != INF) {
h[i] += dis[i];
}
for(int x = t; x != s; x = prevv[x]) {
f = min(f, es[preve[x]].cup - es[preve[x]].flow);
}
for(int x = t; x != s; x = prevv[x]) {
es[preve[x]].flow += f;
es[preve[x] ^ 1].flow -= f;
}
maxf += f;
minc += f * h[t];
}
return tuple<ll, ll>(maxf, minc);
}
};
};
using namespace Primal_Dual;
void solve() {
int n, m;
cin >> n >> m;
vector<string> citys(n);
map<string, int> mp;
for(int i = 0; i < n; i ++) {
cin >> citys[i];
mp[citys[i]] = i;
}
Graph gra(0, 2 * n - 1);
for(int i = 0; i < n; i ++) {
gra.add_Edge(i * 2, i * 2 + 1, (i == 0 || i == n - 1 ? 2 : 1), -1);
}
for(int i = 0; i < m; i ++) {
string a, b;
cin >> a >> b;
int x = mp[a], y = mp[b];
if(x > y) swap(x, y);
gra.add_Edge(x * 2 + 1, y * 2, INF, 0);
}
const auto [maxf, minc] = gra.maxf_minc();
if(maxf == 2) {
vector<vector<int>> G(n);
vector<int> loop(1, 0);
for(int i = 0; i < gra.m; i += 2) {
const auto& e = gra.es[i];
if(e.from / 2 != e.to / 2 && e.flow) {
G[e.from / 2].push_back(e.to / 2);
G[e.to / 2].push_back(e.from / 2);
}
}
int x = G[0][0], prev = 0;
while(x != 0) {
loop.push_back(x);
for(int i : G[x]) if(i != prev || minc == - 4) {
prev = x;
x = i;
break;
}
}
loop.push_back(0);
cout << loop.size() - 1 << '\n';
for(int i : loop) {
cout << citys[i] << '\n';
}
} else {
cout << "No Solution!\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int _ = 1;
// cin >> _;
while(_ --) {
solve();
}
}