首页 > 其他分享 >[SDOI2009] 晨跑 题解

[SDOI2009] 晨跑 题解

时间:2024-05-19 11:10:16浏览次数:23  
标签:nxt int 题解 晨跑 flw vis lst SDOI2009 dis

每个点拆成入点和出点。

发现每个点、每条边都只能经过一次,所以所有边的容量都是 \(1\)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=405,M=1e5+5;
int n,m,s,t,k=1,h[N],vis[N];
int to[M],nxt[M],w[M],f[M];
int lst[N],flw[N],dis[N];
void add(int x,int y,int z,int a){
    w[++k]=z;f[k]=a;to[k]=y;
    nxt[k]=h[x];h[x]=k;
    f[++k]=-a;to[k]=x;
    nxt[k]=h[y];h[y]=k;
}queue<int>q;
int spfa(){
    while(q.size()) q.pop();
    memset(lst,-1,sizeof(lst));
    memset(vis,0,sizeof(vis));
    memset(dis,127,sizeof(dis));
    flw[s]=1e9;dis[s]=0;q.push(s);
    while(q.size()){
        int x=q.front();
        q.pop();vis[x]=0;
        for(int i=h[x];i;i=nxt[i]){
            int y=to[i],vl=w[i];
            if(vl&&dis[y]>dis[x]+f[i]){
                lst[y]=i;
                flw[y]=min(flw[x],vl);
                dis[y]=dis[x]+f[i];
                if(!vis[y])
                    q.push(y),vis[y]=1;
            }
        }
    }return lst[t]!=-1;
}int mxflw,mncst;
void MCMF(){
    while(spfa()){
        mxflw+=flw[t];
        mncst+=dis[t]*flw[t];
        for(int i=t;i!=s;i=to[lst[i]^1])
            w[lst[i]]-=flw[t],w[lst[i]^1]+=flw[t];
    }
}signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;s=n+1;t=n;
    for(int i=2;i<n;i++)
        add(i,i+n,1,0);
    for(int i=1;i<=m;i++){
        int u,v,y;
        cin>>u>>v>>y;
        add(u+n,v,1,y);
    }MCMF();cout<<mxflw<<" "<<mncst;
    return 0;
}//spfa:它没有死透

标签:nxt,int,题解,晨跑,flw,vis,lst,SDOI2009,dis
From: https://www.cnblogs.com/chang-an-22-lyh/p/18200134/sdoi2009-chengpao_tj

相关文章

  • [SDOI2016] 数字配对 题解
    发现题目中描述的配对条件可以理解为:\(pc_i-pc_j=1\)且\(a_i\bmoda_j=0\),其中\(pc_i\)表示\(a_i\)的质因数个数。自然想到以\(pc\)奇偶性建立二分图,可以配对的点间连一条边。先不考虑费用,三种边为:\((s,i,b_i)\),其中\(pc_i\bmod2=1\)。\((i,t,b_i)\),其中\(pc_i\bm......
  • Codeforces 401B Sereja and Contests 题解
    题目简述Sereja是一名程序员,他喜欢参加Codesorfes比赛。不过,乌兹兰的网络连接不太好,所以Sereja有时会跳过比赛。Codesorfes有两种类型的比赛,分为Div1和Div2。Div1和Div2这两轮可以同时进行(Div1轮不能在没有Div2的情况下进行)。每一轮都有一个唯一的标识符,各轮按......
  • 第二届“重科杯”重庆科技大学程序设计竞赛(同步赛)ptlks的题解(2024.5.18)
    A.Alice和Bob题意:给定序列A和序列,m组信息\((i,j)\),Alice可以交换\(A_i\)和\(A_j\)任意次,判断Alice是否能将序列A转变为序列B。思路由于Alice可以任意调整m组信息,所以题目所给m组信息\((i,j)\)不影响结果。先考虑k组信息,第i组为\((T_i,T_{i+1})\),\(1\leqT_1\ltT_2\lt.........
  • [ABC353F] Tile Distance 题解
    [ABC353F]TileDistance题解题目传送门:洛谷,AtcoderSolution很恶心人的分类讨论题。很显然走大格子大概率比走小格子快。对终点和起点向上下左右枚举大格子,我们就把问题转化为给两个大格子\((a,b)\)、\((c,d)\),求怎样走最快。对角的大格子可以通过\(2\)步相互到达,如下......
  • CF527E Data Center Drama 题解
    @目录题目题意题解思路详解注意事项代码AC记录尾声题目CF527EDataCenterDrama·戳这里题意给定一张$n$个点$m$条边的连通无向图。你需要加尽可能少的边,然后给所有边定向,使得每一个点的出入度都是偶数。边可以是自环,也可以有重边。$n\le10^5$,$m\le2\times1......
  • Codeforces 769B News About Credit 题解
    题目简述波利卡普在由$n$名学生(包括他自己)组成的小组中学习,编号为$1$到$n$,波利卡普的编号始终是$1$。他们都在社交网络上注册,每个学生都有一个值$a_i$,表示第$i$名学生每天能发送的最大信息数。清晨,波利卡普知道了一个重要消息,他认为有必要通过私人消息紧急通知所有组员......
  • 安装vue/cli报错问题解决
    在管理员终端中输入命令:npmi-g@vue/cli错误原因证书已过期,需要安装淘宝镜像npmconfigsetregistryhttps://registry.npmmirror.com使用cnpm安装脚手架报错cnpmi-g@vue/cli 这个错误表明你尝试执行的 cnpm 命令无法加载,因为PowerShell策略不允许执......
  • P10125 「Daily OI Round 3」Simple 题解
    题目传送门简单模拟,主要考察字符串。首先输入一个char类型的数组,然后直接遍历每一位是否为Acoipp或Svpoll即可。//Simple//codeby:cq_irritater//time:2024/02/04#include<bits/stdc++.h>usingnamespacestd;chara[10];intmain(){//freopen("......
  • P8684 [蓝桥杯 2019 省 B] 灵能传输 题解
    题目传送门本题涉及到了\(3\)种算法:前缀和,排序以及贪心。(1)前缀和本题实际上要求通过某种灵能传输可以使得该序列的最大值最小。而由前缀和可知,当某一个前缀和序列保持有序(或前缀和序列表示的函数单调)时,其\(s[i]-s[i-1]\)的最大值可以达到最小。通过对几个样例的观察......
  • P9686 Judg. 题解
    题目传送门一道简单模拟。这道题最简单的方法就是直接在for循环中判断题目给出状态是否为AC,如果不是则输出当前\(i\)的值,否则就不输出。#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+10;intn;stringa[MAXN];intmain(){ scanf("%......