[BZOJ 3876] 支线剧情

发布于2016年03月22日 | 暂无评论 | 1,148阅读 | 有上下界网络流,费用流

题目描述

宅男JYY非常喜欢玩RPG游戏，比如仙剑，轩辕剑等等。不过JYY喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在JYY想花费最少的时间看完所有的支线剧情。

JYY现在所玩的RPG游戏中，一共有N个剧情点，由1到N编号，第i个剧情点可以根据JYY的不同的选择，而经过不同的支线剧情，前往Ki种不同的新的剧情点。当然如果为0，则说明i号剧情点是游戏的一个结局了。

JYY观看一个支线剧情需要一定的时间。JYY一开始处在1号剧情点，也就是游戏的开始。显然任何一个剧情点都是从1号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。由于JYY过度使用修改器，导致游戏的“存档”和“读档”功能损坏了，所以JYY要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到1号剧情点。JYY可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情是很痛苦，JYY希望花费最少的时间，看完所有不同的支线剧情。

输入格式

输入一行包含一个正整数N。

接下来N行，第i行为i号剧情点的信息；第一个整数为，接下来个整数对，Bij和Tij，表示从剧情点i可以前往剧情点，并且观看这段支线剧情需要花费的时间。

输出格式

输出一行包含一个整数，表示JYY看完所有支线剧情所需要的最少时间。

题目解析

有1号剧情点，于是便有了源；有结束位置，于是便有了汇；每个剧情至少经过一次，于是便有了下界；每个剧情需要一定时间，于是便有了费用。合起来，它们就是有源汇有上下界最小费用流。

根据有上下界网络流的经典建模方法直接上即可。可参考有上下界网络流。

/**************************************************************
    Problem: 3876
    User: frank_c1
    Language: C++
    Result: Accepted
    Time:9920 ms
    Memory:3096 kb
****************************************************************/
 
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
      
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
struct edge {
    int next,to,cap,cost;
};
 
const int maxn=305;
const int siz=500000;
const int INF=(int)(1e9);
int fr[maxn];
edge e[maxn*maxn];
int d[maxn],p[maxn],a[maxn];
bool inq[maxn];
int n,m,s,t,fl,cs,tote=-1;
 
inline void addone(int u,int v,int c,int s) {
    ++tote;
    e[tote].next=fr[u];fr[u]=tote;
    e[tote].to=v;e[tote].cap=c;e[tote].cost=s;
}
 
inline void addedge(int u,int v,int c,int s) {
    addone(u,v,c,s);addone(v,u,0,-s);
}
 
int q[maxn*maxn],l,r;
bool SPFA() {
    REP(i,1,n+3) d[i]=INF;
    d[s]=p[s]=0;a[s]=INF;inq[s]=1;
    l=1;r=0;q[++r]=s;
    for(;l<=r;) {
        int x=q[l++];
        inq[x]=0;
        RAL(i,x) if(e[i].cap>0 && d[e[i].to]>d[x]+e[i].cost) {
            d[e[i].to]=d[x]+e[i].cost;
            p[e[i].to]=i;
            a[e[i].to]=min(a[x],e[i].cap);
            if(!inq[e[i].to]) {
                if(d[e[i].to]<d[l])
                    q[--l]=e[i].to;
                else q[++r]=e[i].to;
                inq[e[i].to]=1;
            }
        }
    }
    if(d[t]==INF) return 0;
    fl+=a[t];cs+=a[t]*d[t];
    int x=t;
    while(x!=s) {
        e[p[x]].cap-=a[t];
        e[p[x]^1].cap+=a[t];
        x=e[p[x]^1].to;
    }
    return 1;
}
 
void mincost() {
    fl=cs=0;while(SPFA());
}
 
int main() {
    int a,w;
    read(n);
    s=n+2;t=n+3;
    memset(fr,-1,sizeof(fr));
    REP(i,1,n) {
        if(i!=1) addedge(i,n+1,INF,0);
        read(m);
        REP(j,1,m) {
            read(a);read(w);
            addedge(i,a,INF,w);
            addedge(s,a,1,w);
            addedge(i,t,1,0);
        }
    }
    addedge(n+1,1,INF,0);
    mincost();
    printf("%d\n",cs);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

/**************************************************************

Problem: 3876

User: frank_c1

Language: C++

Result: Accepted

Time:9920 ms

Memory:3096 kb

****************************************************************/

#include <set>

#include <map>

#include <queue>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <bitset>

#include <cstring>

#include <cstdlib>

#include <utility>

#include <iostream>

#include <algorithm>

#define REP(i,a,b) for(int i=(a);i<=(b);i++)

#define PER(i,a,b) for(int i=(a);i>=(b);i--)

#define RVC(i,S) for(int i=0;i<(S).size();i++)

#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)

using namespace std;

typedef long long LL;

typedef pair<int,int> pii;

template<class T> inline

void read(T& num) {

bool start=false,neg=false;

char c;

num=0;

while((c=getchar())!=EOF) {

if(c=='-') start=neg=true;

else if(c>='0' && c<='9') {

start=true;

num=num*10+c-'0';

} else if(start) break;

}

if(neg) num=-num;

}

/*============ Header Template ============*/

struct edge {

int next,to,cap,cost;

};

const int maxn=305;

const int siz=500000;

const int INF=(int)(1e9);

int fr[maxn];

edge e[maxn*maxn];

int d[maxn],p[maxn],a[maxn];

bool inq[maxn];

int n,m,s,t,fl,cs,tote=-1;

inline void addone(int u,int v,int c,int s) {

++tote;

e[tote].next=fr[u];fr[u]=tote;

e[tote].to=v;e[tote].cap=c;e[tote].cost=s;

}

inline void addedge(int u,int v,int c,int s) {

addone(u,v,c,s);addone(v,u,0,-s);

}

int q[maxn*maxn],l,r;

bool SPFA() {

REP(i,1,n+3) d[i]=INF;

d[s]=p[s]=0;a[s]=INF;inq[s]=1;

l=1;r=0;q[++r]=s;

for(;l<=r;) {

int x=q[l++];

inq[x]=0;

RAL(i,x) if(e[i].cap>0 && d[e[i].to]>d[x]+e[i].cost) {

d[e[i].to]=d[x]+e[i].cost;

p[e[i].to]=i;

a[e[i].to]=min(a[x],e[i].cap);

if(!inq[e[i].to]) {

if(d[e[i].to]<d[l])

q[--l]=e[i].to;

else q[++r]=e[i].to;

inq[e[i].to]=1;

}

if(d[t]==INF) return 0;

fl+=a[t];cs+=a[t]*d[t];

int x=t;

while(x!=s) {

e[p[x]].cap-=a[t];

e[p[x]^1].cap+=a[t];

x=e[p[x]^1].to;

}

return 1;

}

void mincost() {

fl=cs=0;while(SPFA());

}

int main() {

int a,w;

read(n);

s=n+2;t=n+3;

memset(fr,-1,sizeof(fr));

REP(i,1,n) {

if(i!=1) addedge(i,n+1,INF,0);

read(m);

REP(j,1,m) {

read(a);read(w);

addedge(i,a,INF,w);

addedge(s,a,1,w);

addedge(i,t,1,0);

}

addedge(n+1,1,INF,0);

mincost();

printf("%d\n",cs);

return 0;

}

AC. 梦想

[BZOJ 3876] 支线剧情

题目描述

输入格式

输出格式

题目解析

快速访问

随便看看

友情链接

标签