P6577sol-叛逆
Yanami_Anna · · 题解
upd on 2023.10.27:感谢提醒,现在代码已能够顺利通过。
upd on 2024.1.8:增加网络单纯形费用流,同时修改了 EK 费用流的卡常技巧 4 中的错误。
KM?狗都不学。
卡我费用流?卡啊!怎么不卡了????
首先这种最大权完美匹配的题,首先是完美匹配然后再是最大权,我们伟大的费用流正好可以解决这一类的问题,你只需要源点向左部点连
可惜总有不知好歹的模板题喜欢逆时代的潮流出能够卡掉我们伟大费用流的弱智数据范围,我们身为正义的化身,网络流算法的传教士,当然要制止这种恶心所有人的行为,在费用流的铁拳之下没有什么算法还能够优化!!!!
这里隆重请出我们费用流卡常一哥,原始对偶算法!!!!!!!
他的原理是这样的,如果你写过约翰逊全源最短路应该比较清楚,我们面对弱智负边权是怎么粉碎负边权的阴谋的,没错,我们给每个点赋了一个势能
我们平时费用流写的都是 EK,然后把里面的 bfs 换成贝尔曼福德找一下最短的增广路,这样一次增广的时间复杂度是最坏
但是费用流有一点不一样,他残量网络时刻在变化,可恶的反边,可惜就算你图再怎么变我伟大的小常数迪杰斯特拉也能在增广之后完成点势能的更新,怎么做呢?
我们增广一次顺手求出了所有点到源点的距离,而点势能的更新?根本不在乎,我们直接给所有势能加一个最短路的长度,然后直接更新边权,这样做就是对的,这世间,还有什么能够阻挡!!!!!还有什么能够阻挡我们的费用流算法!!!!!!!!!
时间复杂度
下面是一些卡常小技巧。
- 如果你拥有封装 class 的好习惯,请把他丢掉,因为 class 会比较慢。
- 如果你拥有链式前向星建图的好习惯,请把他丢掉,直接用 vector 建图,邻接矩阵存流量和费用会更快。
- 如果你拥有
#define int long long
的好习惯,请把他丢掉,因为这个东西巨慢无比。 - 如果你拥有小值域变量开 int 的好习惯,请把他丢掉,short 运算速度比 int 快。
- 如果你拥有写 scanf 和 printf 的好习惯,请把他丢掉,写个快读吧。
-
大概就是上面这样。
#include <bits/stdc++.h>
using namespace std;
int read()
{
int s = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
{
w = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
int match[505];
int cnt = 1;
vector<int> ljb[1005];
int cost[1005][1005];
bool flow[1005][1005];
long long anscost;
inline void addedge(int u, int v, int fl, int co)
{
cnt++;
flow[u][v] = fl;
cost[u][v] = co;
ljb[u].push_back(v);
return;
}
inline void Add(int u, int v, int fl, int co)
{
addedge(u, v, fl, co);
addedge(v, u, 0, -co);
return;
}
bool in[1005];
long long dis[1005];
int S, T, N;
inline void SPFA()
{
for (int i = 1; i <= N; i++)
{
dis[i] = 1e18;
}
dis[S] = 0;
queue<int> q;
q.push(S);
while (!q.empty())
{
int t = q.front();
// printf("%lld\n",t);
q.pop();
in[t] = false;
for (int i = 0; i < ljb[t].size(); ++i)
{
int v = ljb[t][i];
int fl = flow[t][v];
int co = cost[t][v];
if (fl && dis[t] + co < dis[v])
{
dis[v] = dis[t] + co;
if (!in[v])
{
q.push(v);
in[v] = true;
}
}
}
}
return;
}
int pre[1005];
bool vis[1005];
long long h[1005];
int Pre[1005];
int Nxt[1005];
inline bool dijkstra()
{
int fvv = N;
Nxt[0] = 1;
for (int i = 1; i <= N; ++i)
{
vis[i] = false;
dis[i] = 1e18;
Pre[i] = i - 1;
Nxt[i] = i + 1;
}
dis[S] = 0;
while (fvv--)
{
int cur = 0;
for (int i = Nxt[0]; i <= N; i = Nxt[i])
{
if (!vis[i])
{
if (!cur)
cur = i;
else if (dis[i] < dis[cur])
{
cur = i;
}
}
}
vis[cur] = true;
Nxt[Pre[cur]] = Nxt[cur];
Pre[Nxt[cur]] = Pre[cur];
for (int j = 0; j < ljb[cur].size(); ++j)
{
int v = ljb[cur][j];
int fl = flow[cur][v];
int co = cost[cur][v] + h[cur] - h[v];
if (fl && dis[cur] + co < dis[v])
{
dis[v] = dis[cur] + co;
pre[v] = cur;
}
}
}
return dis[T] < 1000000000000000000ll;
}
inline void EK()
{
SPFA();
for (int i = 1; i <= N; i++)
{
h[i] = dis[i];
}
long long cnt = 0;
while (dijkstra())
{
int now = T;
for (int i = 1; i <= N; i++)
h[i] += dis[i];
cnt = 0;
while (pre[now])
{
flow[pre[now]][now] = false;
flow[now][pre[now]] = true;
cnt += cost[pre[now]][now];
now = pre[now];
}
anscost += cnt;
}
return;
}
int n, m;
signed main()
{
n = read(), m = read();
S = 2 * n + 1;
T = 2 * n + 2;
N = 2 * n + 2;
int u, v, w;
for (int i = 1; i <= m; i++)
{
u = read(), v = read(), w = read();
Add(u, v + n, 1, -w);
}
for (int i = 1; i <= n; i++)
{
Add(S, i, 1, 0);
Add(i + n, T, 1, 0);
}
EK();
printf("%lld\n", -anscost);
for (int i = n + 1; i <= 2 * n; i++)
{
for (int j = 0; j < ljb[i].size(); ++j)
{
int v = ljb[i][j];
if (v == T)
continue;
if (flow[i][v])
{
match[i - n] = v;
break;
}
}
}
for (int i = 1; i <= n; i++)
{
printf("%d ", match[i]);
}
return 0;
}
这个题如果用 EK 或者 dinic 那就只能卡到这个水平,但是费用流又不是只有这个水平,我们还可以使用网络单纯形来跑费用流。
这个算法可以从 这里 和 这里 学习,我太菜了感觉讲不明白就不献丑了。
用这个跑这个题然后加个快读就随手最优解了。(截止于 2024.1.8)
甩了第二的 KM 整整 150ms,KM 算法没有未来!
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
inline int read()
{
int d=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {d=d*10+c-48;c=getchar();}
return d*f;
}
class SimpleX{
public:
const int inf=1e12;
int head[1005];
int nxt[502005];
short from[502005];
short to[502005];
short flow[502005];
int cost[502005];
int cnt=1;
void addedge(int u,int v,int fl,int co){
cnt++;
to[cnt]=v;
from[cnt]=u;//
nxt[cnt]=head[u];
head[u]=cnt;
flow[cnt]=fl;
cost[cnt]=co;
return;
}
void Add(int u,int v,int fl,int co){
addedge(u,v,fl,co);
addedge(v,u,0,-co);
return;
}
short fa[1005];
int fe[1005];
int tag[1005];
int pos;
void gettree(int cur){
tag[cur]=pos;
for(int i=head[cur];i;i=nxt[i]){
int v=to[i];
if(tag[v]||!flow[i])continue;
fa[v]=cur;
fe[v]=i;
gettree(v);
}
}
int pushflow(int id){
pos++;
int u=from[id],v=to[id];
int lca=u;
while(lca){
tag[lca]=pos;
lca=fa[lca];
}
lca=v;
while(tag[lca]!=pos){
tag[lca]=pos;
lca=fa[lca];
}
int p=2,minflow=flow[id],del;
for(int now=u;now^lca;now=fa[now]){
int eg=fe[now];
if(flow[eg]<minflow){
p=0;
minflow=flow[eg];
del=now;
}
}
for(int now=v;now^lca;now=fa[now]){//
int eg=fe[now]^1;
if(flow[eg]<minflow){
p=1;
minflow=flow[eg];
del=now;
}
}
int C=0;
for(int now=u;now^lca;now=fa[now]){
int eg=fe[now];
flow[eg]-=minflow;
flow[eg^1]+=minflow;
C=(C+minflow*cost[eg]);
}
for(int now=v;now^lca;now=fa[now]){
int eg=fe[now]^1;
flow[eg]-=minflow;
flow[eg^1]+=minflow;
C=(C+minflow*cost[eg]);
}
flow[id]-=minflow;
flow[id^1]+=minflow;
C=(C+minflow*cost[id]);
if(p==2){
return C;
}
if(p)swap(u,v);
int Le=id^p,Lu=v;
while(Lu!=del){
Le^=1;
tag[u]=0;
swap(fe[u],Le);
int need=fa[u];
fa[u]=Lu;
Lu=u;
u=need;
}
return C;
}
int dep[1005];
int getdep(int x){
if(tag[x]==pos)return dep[x];
tag[x]=pos;
return dep[x]=getdep(fa[x])+cost[fe[x]];
}
pair<int,int> getflow(int s,int t){
Add(t,s,inf,-inf);
pos++;
gettree(t);
fa[t]=0;
pos++;
tag[t]=pos;
bool flag=true;
while(flag){
flag=false;
for(int i=2;i<=cnt;i++){
int u=from[i],v=to[i];
if(!flow[i])continue;
if(cost[i]+getdep(u)-getdep(v)<0){
flag=true;
pushflow(i);
}
}
}
long long ansflow=flow[cnt];
long long anscost=0;
for(int i=2;i<=cnt;i+=2){
anscost=anscost+flow[i^1]*cost[i];
}
return make_pair(ansflow,anscost+(ansflow*inf));
}
}G;
int n,m;
int pre[505];
signed main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u,v,w;
u=read(),v=read(),w=read();
G.Add(u,v+n,1,-w);
}
int s=2*n+1,t=2*n+2;
for(int i=1;i<=n;i++){
G.Add(s,i,1,0);
G.Add(i+n,t,1,0);
}
printf("%lld\n",-G.getflow(s,t).second);
for(int i=2;i<=G.cnt;i+=2){
if(G.flow[i^1]){
if(G.from[i]==s||G.to[i]==t)continue;
pre[G.to[i]-n]=G.from[i];
}
}
for(int i=1;i<=n;i++){
printf("%lld ",pre[i]);
}
puts("");
return 0;
}