3876: [Ahoi2014]支线剧情
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1538 Solved: 940
[Submit][Status][Discuss]
Description
Input
Output
输出一行包含一个整数,表示JYY看完所有支线剧情所需要的最少时间。
Sample Input
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0
Sample Output
HINT
JYY需要重新开始3次游戏,加上一开始的一次游戏,4次游戏的进程是
Source
题意:给定一个DAG,1为起始点,任意一个点可以直接回到1,每条边有经过代价,求一种最优方案使得每条边至少经过一次,代价最小。
暴力:枚举终点,非严格次短路更新。
时间复杂度:O(p*s*nlogn){p为终点数,s为1->一终点路径上点的出度的乘积,nlogn为堆优化的dijkstra的时间}
考虑极端情况:s可以达到2^n(可以想象成一个树,树根为1,叶子节点全都只连同一个节点)
显然:TLE
正解:无源汇有下界最小费用可行流。
具体建图如下:
对于x->y,费用为z
S向y建容量为1,费用为z的边(对应无源汇里的入度处理)
x向y建容量INF,费用为z的边(即*流)
对于每一个点x,假设其出度为a
x向T建容量为a,费用为0的边(出度处理)(注意这里不要加上费用,因为已经在入度处理的时候就加过了)
x向1建容量INF,费用为0的边(对应题意)
然后跑最小费用流就可以了。
#include<cstdio>
#include<cstring>
#include<iostream>
#define EF if(ch==EOF) return x;
using namespace std;
const int N=5e4+;
const int inf=2e9;
struct data{int x,y;}f[N];
struct edge{int v,next,cap,cost;}e[N<<];int tot=,head[N];
int n,m,cnt,ans,S,T,rd[N],cd[N],dis[N],pre[N],q[N<<];bool vis[N];
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;EF;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void add(int x,int y,int z,int cost=){
e[++tot].v=y;e[tot].cap=z;e[tot].cost=cost;e[tot].next=head[x];head[x]=tot;
e[++tot].v=x;e[tot].cap=;e[tot].cost=-cost;e[tot].next=head[y];head[y]=tot;
}
bool spfa(){
memset(vis,,sizeof vis);
memset(dis,0x3f,sizeof dis);
unsigned short h=,t=;q[t]=S;dis[S]=;vis[S]=;
while(h!=t){
int x=q[++h];vis[x]=;
for(int i=head[x];i;i=e[i].next){
if(e[i].cap&&dis[e[i].v]>dis[x]+e[i].cost){
dis[e[i].v]=dis[x]+e[i].cost;
pre[e[i].v]=i;
if(!vis[e[i].v]){
vis[e[i].v]=;
q[++t]=e[i].v;
}
}
}
}
return dis[T]<0x3f3f3f3f;
}
int augment(){
int flow=0x3f3f3f3f;
for(int i=T;i!=S;i=e[pre[i]^].v) flow=min(flow,e[pre[i]].cap);
for(int i=T;i!=S;i=e[pre[i]^].v){
e[pre[i]].cap-=flow;
e[pre[i]^].cap+=flow;
}
return dis[T]*flow;
}
void MCMF(){
while(spfa()) ans+=augment();
}
int main(){
n=read();S=,T=n+;
for(int i=,x,y,z;i<=n;i++){
x=read();cd[i]=x;
if(i!=) add(i,,inf);
while(x--) y=read(),z=read(),ans+=z,rd[y]++,add(i,y,inf,z);
}
for(int i=;i<=n;i++){
if(rd[i]>cd[i]) add(S,i,rd[i]-cd[i]);
else add(i,T,cd[i]-rd[i]);
}
MCMF();
printf("%d",ans);
return ;
}
实际上有一个很大的建图优化,也是无源汇建图的优化,即合并入出度并且相互抵消。但是对于这道题就不好做,因为有费用,不过可以这么想:既然每一条边都要走,我们就直接把费用抽出来,即答案一开始就为所有边走一次的代价,然后这样入度的费用就变为0了。然后再与出度进行抵消,最后边的数量大大减少。