题解：P1006 [NOIP 2008 提高组] 传纸条

· · 题解

可以费用流，但是疑惑的是题解区没有费用流。

我们发现，这要找两条路去传纸条，而每个人有个好心程度且只能传一次。

于是很容易设计费用流，对于每个点流量为 1，费用为那个点的好心程度。

每个边流量为 1，费用为 0。

跑最大费用最大流，设 s 为起点，t 为终点。

因为小渊传完后需要回传，所以 s=t，但是这样 s=t 就直接死循环了。

并且在费用流中，点，是不能有流量和费用的。

那咋办，我们化点为边。

可以这样，把点拆成一个入点和一个出点。

入点指向出点的边流量和费用就是我们之前讨论的那个点的。

每个那个点的入点都指向它的入边，出边同样。

我们 s 设为小渊的出点，t 为小渊的入点，也能避免死循环的问题。

跑最大费用最大流刚好满足题意。

代码。

//Dinic 算法  
#include<bits/stdc++.h>
using namespace std;
// #define int long long
int n,m,s,t;
int head[80010],to[240010],nxt[240010],val[240010],cost[240010],tot=1;
void add(int u,int v,int w,int c){
    to[++tot]=v,val[tot]=w,cost[tot]=c;
    nxt[tot]=head[u];
    head[u]=tot;
}
int maxflow,maxcost,dis[80010],now[80010],cnt[80010];
bool vis[80010];
bool spfa(){
    list<int>q;
    memset(dis,-0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    vis[s]=dis[s]=0,now[s]=head[s];
    q.push_back(s);
    while(!q.empty()){
        int u=q.front();
        q.pop_front();
        vis[u]=0;
        for(int i=head[u];i;i=nxt[i]){
            now[to[i]]=head[to[i]];
            if(!val[i]) continue;
            if(dis[to[i]]<dis[u]+cost[i]){
                dis[to[i]]=dis[u]+cost[i];
                cnt[to[i]]=cnt[u]+1;
                if(vis[to[i]]) continue;
                vis[to[i]]=1;
                if(dis[to[i]]<dis[q.empty() ? 0 :q.front()]) q.push_front(to[i]);
                else q.push_back(to[i]);
            }
        }
    }
    memset(vis,0,sizeof vis);
    return dis[t]>dis[0]/2;
}
int dinic(int x,int flow){
    vis[x]=1;
    if(x==t) return flow;
    int rest=flow;
    for(int i=now[x];i && rest;i=nxt[i]){
        now[x]=i;
        if(dis[to[i]]!=dis[x]+cost[i] || !val[i] || vis[to[i]]) continue;
        int v=dinic(to[i],min(rest,val[i]));
        if(!v) dis[to[i]]=dis[0];
        val[i]-=v,val[i^1]+=v,maxcost+=cost[i]*v;
        rest-=v;
    }
    return flow-rest;
}
namespace Input{
    int a[210][210];
    void main() {
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
    }
}
int get(int x,int y,int k){
    return (x-1)*m+y+k*n*m;
}
signed main() {
    ios::sync_with_stdio(0);
    cin>>n>>m;
    s=n*m+1,t=n*m;
    Input::main();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            add(get(i,j,0),get(i,j,1),1,Input::a[i][j]),add(get(i,j,1),get(i,j,0),0,-Input::a[i][j]);
            if(i<n) add(get(i,j,1),get(i+1,j,0),1,0),add(get(i+1,j,0),get(i,j,1),0,0);
            if(j<m) add(get(i,j,1),get(i,j+1,0),1,0),add(get(i,j+1,0),get(i,j,1),0,0);
        }
    }
    int flow=0;
    while(spfa()) while(flow=dinic(s,1e18)) maxflow+=flow;
    cout<<maxcost;
    return 0;
}

此代码能过 ouuan 的大教室中传纸条。