Luogu

分析

题目很像路径覆盖,因此可以考虑网络流。

令 $1$ 号点为源点,再新建一个汇点,然后连边:

  • 如果 $u$ 能到 $v$,从 $u$ 向 $v$ 连一条下界为 $1$,上界为 $+\infty$,费用为 $t$ 的边,表示至少要看一次这段剧情,看一次需要花 $t$ 的时间。
  • 所有点向汇点连一条下界为 $0$,上界为 $+\infty$,费用为 $0$ 的边。

然后求有源汇有上下界最小费用可行流即可。注意求出来的最小费用没有把强制补到下界的那些流量算进去,需要自己加到答案里去。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300+10,M=100000+10;
const int inf=0x3f3f3f3f;

int n,m,d[N];

struct edge { int v,w,c,nxt; } e[M<<1];
int head[N];
inline void addEdge(int u,int v,int w,int c) {
    static int cnt=1;
    e[++cnt]=(edge){v,w,c,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,0,-c,head[v]},head[v]=cnt;
}
inline void add(int u,int v,int l,int r,int c) {
    addEdge(u,v,r-l,c),d[v]+=l,d[u]-=l;
}

int s,t,S,T;
int dis[N],inq[N],lst[N];
inline int spfa() {
    memset(dis,0x3f,sizeof(dis)),memset(lst,0,sizeof(lst));
    queue<int> Q; Q.push(S),dis[S]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(),inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w,c=e[i].c;
            if (w&&dis[u]+c<dis[v]) {
                dis[v]=dis[u]+c,lst[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return lst[T]!=0;
}

int main() {
    n=read(); s=1,t=n+1,S=n+2,T=n+3; int ans=0;
    for (re int u=1;u<=n;++u) {
        for (re int k=read();k;--k) {
            int v=read(),t=read();
            add(u,v,1,inf,t),ans+=t;
        }
    }
    for (re int i=1;i<=n;++i) add(i,t,0,inf,0);
    addEdge(t,s,inf,0);
    for (re int i=s;i<=t;++i) {
        if (d[i]>0) addEdge(S,i,d[i],0);
        if (d[i]<0) addEdge(i,T,-d[i],0);
    }
    while (spfa()) {
        int f=inf;
        for (re int i=lst[T];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=lst[T];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        ans+=dis[T]*f;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 02 月 26 日 06 : 16 PM