P6577sol-叛逆

· · 题解

upd on 2023.10.27：感谢提醒，现在代码已能够顺利通过。

upd on 2024.1.8：增加网络单纯形费用流，同时修改了 EK 费用流的卡常技巧 4 中的错误。

KM？狗都不学。

卡我费用流？卡啊！怎么不卡了？？？？

首先这种最大权完美匹配的题，首先是完美匹配然后再是最大权，我们伟大的费用流正好可以解决这一类的问题，你只需要源点向左部点连 (1,0) 的边，左部点向右部点连 (1,-w) 的边，右部点向汇点连 (1,0) 的边然后跑最小费用最大流就可以轻松解决这个问题了。

可惜总有不知好歹的模板题喜欢逆时代的潮流出能够卡掉我们伟大费用流的弱智数据范围，我们身为正义的化身，网络流算法的传教士，当然要制止这种恶心所有人的行为，在费用流的铁拳之下没有什么算法还能够优化！！！！

这里隆重请出我们费用流卡常一哥，原始对偶算法！！！！！！！

他的原理是这样的，如果你写过约翰逊全源最短路应该比较清楚，我们面对弱智负边权是怎么粉碎负边权的阴谋的，没错，我们给每个点赋了一个势能 h，这个势能约翰逊是直接设成单源最短路的路径长度的，然后把有向边 (u,v,w) 的边权变成 w+h_u-h_v，根据三角不等式可以证明出这样操作后所有边权非负并且两点间的最短路的变化只和两个点的势能有关，那我们这样子跑一个迪杰斯特拉就整个能把最短路直接算出来了。

我们平时费用流写的都是 EK，然后把里面的 bfs 换成贝尔曼福德找一下最短的增广路，这样一次增广的时间复杂度是最坏 O(nm) 的，这个时间复杂度非常废物，我们怎么能屈服于负数边权的淫威之下，看我们首先跑一遍贝尔曼福德，然后直接赋值势能更换边权，残量网络已然是我迪杰斯特拉的天下！！！堆优化只会影响我增广的速度，直接丢掉，我 O(n^2) 的找最短增广路之后时间复杂度就已经是伟大的 O(n^3) 了！

但是费用流有一点不一样，他残量网络时刻在变化，可恶的反边，可惜就算你图再怎么变我伟大的小常数迪杰斯特拉也能在增广之后完成点势能的更新，怎么做呢？

我们增广一次顺手求出了所有点到源点的距离，而点势能的更新？根本不在乎，我们直接给所有势能加一个最短路的长度，然后直接更新边权，这样做就是对的，这世间，还有什么能够阻挡！！！！！还有什么能够阻挡我们的费用流算法！！！！！！！！！

时间复杂度 O(n^3)，可能还有一点小常数不过没有人在乎，这就是网络流算法的魅力，KM 算法这种又生硬难写又晦涩难懂的逆时代浪潮的算法迟早被淹没在费用流恐怖的实力之下！！！

下面是一些卡常小技巧。

  1. 如果你拥有封装 class 的好习惯，请把他丢掉，因为 class 会比较慢。
  2. 如果你拥有链式前向星建图的好习惯，请把他丢掉，直接用 vector 建图，邻接矩阵存流量和费用会更快。
  3. 如果你拥有 #define int long long 的好习惯，请把他丢掉，因为这个东西巨慢无比。
  4. 如果你拥有小值域变量开 int 的好习惯，请把他丢掉，short 运算速度比 int 快。
  5. 如果你拥有写 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;
}