网络流

Dinic

bool bfs() {
    memset(h,-1,sizeof h);
    int op=0,cl=1;
    h[s]=0;
    q[1]=s;
    while(op<cl) {
        op=(op+1)%M;
        int u=q[op];
        for(int i=head[u]; i!=-1; i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if(w>0 && h[v]==-1) {
                cl=(cl+1)%M;
                q[cl]=v;
                h[v]=h[u]+1;
                if(v==t)return true;
            }
        }
    }
    return h[t]!=-1;
}
int dfs(int u,int flow) {
    if(u==t)return flow;
    int sum=0;
    for(int &i=now[u]; i!=-1; i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if(w>0 && h[v]==h[u]+1) {
            int s1=dfs(v,min(flow,w));
            sum+=s1;
            flow-=s1;
            e[i].w-=s1;
            e[i^1].w+=s1;
            if(flow==0)break;
        }
    }
    return sum;
}
int Dinic() {
    int ans=0;
    while(bfs()) {
        memcpy(now,head,sizeof head);
        ans+=dfs(s,INF);
    }
    return ans;
}

P1251 线性规划

P2053 设置n * m个点来计算重叠的等待时间

P2050 为P2053的动态开点版本

P2764 最小割

P2825 分割连通块

费用流dijkstra与johnson

johnson的原理是：给每个点加上一个势h[u]，使得新图中的边权非负。

证明：由三角形不等式,dis[u]+w>=dis[v] --> w+h[u]-h[v]>=0

如何维护势函数h[]。

初始情况下,如果所有的权值都为正,那么可以简单地将所有h[i]设置为0；如果有负权值,那么我们做一遍spfa,让h[]等于距离函数。

让 \(d'[i]\) 表示\(G'\)中\(S\)到点\(i\)的距离,当某次增广结束后,\(G'\)中会新加入某些边\((j, i)\),而这些\((j, i)\)必定满足\(d'[i] + w'[i][j] = d'[j]\) (否则 \((i, j)\) 就不会在增广路中)。对上式进行一些代数变换：

\[ d'[i] + w'[i][j] = d'[j] \\d'[i] + w[i][j] + h[i]-h[j] = d'[j] \\(d'[j] + h[j])-(d'[i] + h[i])-w[i][j] = 0 \\(d'[j] + h[j])-(d'[i] + h[i]) + w[j][i] = 0 \]

(因为是费用流,所以有w[i][j] = -w[j][i])

因此让所有h[i] += d'[i]后,新加入的边(j, i)也会满足势函数的性质。

同时我们有：

\[ d'[i] + w'[i][j] - d'[j] >= 0\\ d'[i] + h[i] - h[j] + w[i][j] - d'[j] >= 0\\ (d'[i] + h[i]) - (d'[j] + h[j]) + w[i][j] >= 0\\ \]

P4542

这道题困难的地方在于模型的转化，即如何看出"按顺序摧毁根据地"的隐藏条件。

我们设\(d[i][j]\)表示从\(i\)到\(j\)不经过任何编号大于\(i,j\)的点的最短路径。这保证了我们一定可以按照给定的顺序进行更新。

所以用\(Floyd\)预处理出\(d[i][j]\)，然后用费用流求解。

至于建图，因为题目保证一定有解，所以整张图一定联通，不用考虑有的点不被经过；又因为跑的是最大流，所以所有点一定都会被经过，我们只需要限制一下流量不超过\(K\)即可。

这样，设源汇点为\(s,t\)，那么将\(1,2,...,n\)的点与\(s\)连\(w=1\)的边，表示互不相交且只能流向一个点；将\(0\to n\)连\(w=K\)的边，表示最多有\(K\)条路径，最多流向\(K\)个点。

之后，将\(0,1,...,n\)的点拆点，互相连\(w=1\)的边，表示只流向一个满足顺序的点。

最后，将\(0',1',...,n'\)向\(t\)连\(w=1\)的边，没有具体意义，就是强行让他们有一个汇点。

这样跑出来就是最优解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=440,M=4e5+10,INF=0x3f3f3f3f;
struct edge{
    int v,w,f,nxt;
}e[M];
int head[N],pre[N],lst[N],dis[N],vis[N];
int d[N][N];
int n,m,K,cnt,s,t,D,maxflow,mincost,u,v,w;
void add(int u,int v,int w,int f){e[++cnt].v=v,e[cnt].w=w,e[cnt].f=f,e[cnt].nxt=head[u],head[u]=cnt;}
void init(){
    for(int i=0;i<=n;++i){
        d[i][i]=0;
        for(int j=0;j<=n;++j) if(i!=j) d[i][j]=INF;
    }
}
void floyd(){
    for(int k=0;k<=n;++k)
        for(int i=0;i<=n;++i)
            for(int j=0;j<=n;++j)
                if(k<=max(i,j)) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);   
}
void build(){
    s=n*2+10,t=n*2+13,D=n+3;
    for(int i=0;i<=n;++i){
        if(i==0)add(s,i,K,0),add(i,s,0,0);
        else add(s,i,1,0),add(i,s,0,0);
        add(i+D,t,1,0),add(t,i+D,0,0);
        for(int j=i+1;j<=n;++j)add(i,j+D,1,d[i][j]),add(j+D,i,0,-d[i][j]);
    }
}
bool SPFA(){
    queue<int> q;
    memset(vis,0,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    memset(pre,-1,sizeof pre);
    dis[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w,f=e[i].f;
            if(w>0 && dis[v]>dis[u]+f){
                dis[v]=dis[u]+f,pre[v]=u,lst[v]=i;
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
    return pre[t]!=-1;
}
void MCMF(){
    maxflow=0,mincost=0;
    while(SPFA()){
        int minn=INF;
        for(int i=t;i!=s;i=pre[i]) minn=min(minn,e[lst[i]].w);
        for(int i=t;i!=s;i=pre[i]) e[lst[i]].w-=minn,e[lst[i]^1].w+=minn;
        maxflow+=minn,mincost+=minn*dis[t];
    }
}
int main(){
    memset(head,-1,sizeof head);
    cnt=-1;
    scanf("%d%d%d",&n,&m,&K);
    init();
    for(int i=1;i<=m;++i)scanf("%d%d%d",&u,&v,&w),d[u][v]=d[v][u]=min(d[u][v],w);
    floyd();
    build();
    MCMF();
    printf("%d",mincost);
    return 0;
}