[SDOI2009] 晨跑

题意

在加权有向图中求一路径集合 满足

  • 起点为 ,终点为 ,即 .
  • 集合内的路径除了起点终点,互不相交(即不经过相同的点)
  • 对于从 直连的边,只能算一次

要求在最大化路径条数(即 )的前提下,最小化所有路径边权的和

.

分析

比较显然的费用流模型

作为源点, 作为汇点, 的边特判

每个点只能被走一次 拆点建边,容量为 1,费用为 0

对于每一条边 ,连接 ,并使得 .

从源点到汇点跑费用流,加上特判的部分就行了

代码

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1000,M=2e5,INF=0x3f3f3f3f;
int n,m,s,t;

struct qxx{int nex,t,v,c;};
qxx e[M];
int h[N],cnt=1;
void add_path(int f,int t,int v,int c){e[++cnt]=(qxx){h[f],t,v,c},h[f]=cnt;}
void add_flow(int f,int t,int v,int c){add_path(f,t,v,c);add_path(t,f,0,-c);}

int pre[N],incf[N],dis[N];
bool vis[N];
bool bfs(){memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s),incf[s]=INF,incf[t]=0,dis[s]=0;
    while(q.size()){int u=q.front();q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v,&c=e[i].c;
            if(!w||dis[v]<=dis[u]+c)continue;
            dis[v]=dis[u]+c,pre[v]=i,incf[v]=min(w,incf[u]);
            if(!vis[v])q.push(v),vis[v]=1;
        }
    }
    return incf[t];
}
int maxflow,mincost;
void update(){maxflow+=incf[t];
    for(int u=t;u!=s;u=e[pre[u]^1].t){e[pre[u]].v-=incf[t],e[pre[u]^1].v+=incf[t];
        mincost+=incf[t]*e[pre[u]].c;
    }
}
int flag,cost=INF;// 对 1->n 的特判
int main(){scanf("%d%d",&n,&m);
    s=1<<1,t=n<<1;// 必须*2 不然会与其他结点冲突
    for(int i=1,a,b,c;i<=m;i++){scanf("%d%d%d",&a,&b,&c);
        if(a==1&&b==n)flag=1,cost=min(cost,c);
        else if(a==1)add_flow(s,b<<1,1,c);
        else if(b==n)add_flow(a<<1|1,t,1,c);
        else add_flow(a<<1|1,b<<1,1,c);
    }
    for(int i=2;i<n;i++){add_flow(i<<1,i<<1|1,1,0);
    }
    while(bfs())update();
    if(flag)maxflow++,mincost+=cost;
    printf("%d %d",maxflow,mincost);
    return 0;
}
//i->i<<1,i<<1|1
// 源点为 1,汇点为 n(不拆点)。
//1->n 的路径要特判

  转载请注明: Sshwy's Blog [SDOI2009] 晨跑

 上一篇
[CQOI2012] 交换棋子 [CQOI2012] 交换棋子
题意有一个 n 行 m 列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第 i 行第 j 列的格子只能参与 次交换。 求最小交换总次数。如果无解,输出 -1。 分析非
2019.01.14
下一篇 
杜教筛 杜教筛
摘要 莫比乌斯反演推完式子后,一般考虑线性筛和数论分块。当要求在低于线性时间的求解积性函数前缀和的问题的时候就会用到杜教筛。 符号说明简单解释一下本文可能用到的记号的含义。 狄利克雷卷积符号 表示数论函数
2019.01.11
  目录