APIO2009 ATM

2021-05-02 21:28

阅读：637

标签：while inpu opened 开始 size tput add apio2009 algorithm

Input
第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号

Output
输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

Sample Input
6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 
5
1 4
4
3
5
6

Sample Output
47

题目

技术分享

芒果君：缩点+SPFA最长路裸裸的啊，可是我把缩点前后搞混了QAQ

要点权转边权然后就没什么好说的了……

  1 #include  2 #include  3 #include  4 #include
  5 #include  6 #include  7 #include  8 #include  9 #define inf 1 10 #define maxn 500010
 11 using namespace std;
 12 typedef long long ll;
 13 struct Edge{
 14     int v,ne;
 15 }e[maxn],E[maxn];
 16 int cnt,tot,n,m,s,ans,jh[maxn],w[maxn],dis[maxn],dfn[maxn],low[maxn],hl[maxn],vis[maxn],HL[maxn],W[maxn];
 17 stackint>S;
 18 queueint>Q; 
 19 void add(int u,int v)
 20 {
 21     e[++cnt].v=v;
 22     e[cnt].ne=hl[u];
 23     hl[u]=cnt;
 24 }
 25 ll read()
 26 {
 27     ll ret(0),f=1;
 28     char ch=getchar();
 29     while(ch‘0‘||ch>‘9‘){
 30         if(ch==‘-‘) f=-1;
 31         ch=getchar();
 32     }
 33     while(ch>=‘0‘&&ch‘9‘){
 34         ret=ret*10+ch-‘0‘;
 35         ch=getchar();
 36     }
 37     return ret*f;
 38 }
 39 void tarjan(int x)
 40 {
 41     S.push(x);
 42     dfn[x]=low[x]=++cnt;
 43     vis[x]=1;
 44     for(int i=hl[x];i;i=e[i].ne){
 45         int v=e[i].v;
 46         if(!dfn[v]){
 47             tarjan(v);
 48             low[x]=min(low[x],low[v]);
 49         }
 50         else if(vis[v]) low[x]=min(low[x],dfn[v]);
 51     }
 52     if(dfn[x]==low[x]){
 53         tot++;
 54         int now=-1;
 55         while(now!=x){
 56             now=S.top();
 57             S.pop();
 58             jh[now]=tot;
 59             vis[now]=0;
 60         }
 61     }
 62 }
 63 void rebuild()
 64 {
 65     for(int x=1;xx){
 66         for(int i=hl[x];i;i=e[i].ne){
 67             int v=e[i].v;
 68             if(jh[x]==jh[v]) continue;
 69             E[++cnt].v=jh[v];
 70             E[cnt].ne=HL[jh[x]];
 71             HL[jh[x]]=cnt;
 72         }
 73         W[jh[x]]+=w[x];
 74     }
 75 }
 76 void spfa()
 77 {
 78     dis[jh[s]]=W[jh[s]];
 79     Q.push(jh[s]);
 80     while(!Q.empty()){
 81         int x=Q.front();
 82         Q.pop();
 83         vis[x]=0;
 84         for(int i=HL[x];i;i=E[i].ne){
 85             int v=E[i].v;
 86             if(dis[x]+W[v]>dis[v]){
 87                 dis[v]=dis[x]+W[v];
 88                 if(!vis[v]){
 89                     vis[v]=1;
 90                     Q.push(v);
 91                 }
 92             }
 93         }
 94     }
 95 }
 96 int main()
 97 {
 98     int u,v;
 99     n=read(),m=read();
100     for(int i=1;ii){
101         u=read(),v=read();
102         add(u,v);
103     }
104     for(int i=1;iread();
105     s=read(),m=read();
106     cnt=0;
107     for(int i=1;iif(!dfn[i]) tarjan(i);
108     cnt=0;
109     rebuild();
110     spfa();
111     for(int i=1;ii){
112         v=read();
113         ans=max(ans,dis[jh[v]]);
114     }
115     printf("%d",ans);
116     return 0;
117 }

APIO2009 ATM

标签：while inpu opened 开始 size tput add apio2009 algorithm

原文地址：http://www.cnblogs.com/12mango/p/7755751.html

上一篇：Windows 8实用窍门系列：20.Windows 8中的GridView使用(二)和DataTemplateSelector

下一篇：WPF Binding源

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：APIO2009 ATM
文章链接：http://soscw.com/essay/81508.html

亲，登录后才可以留言！

APIO2009 ATM

评论

热门文章

推荐文章

最新文章

置顶文章