比赛 |
20160902 |
评测结果 |
AWAAWAAAAA |
题目名称 |
抢掠计划 |
最终得分 |
80 |
用户昵称 |
农场主 |
运行时间 |
0.068 s |
代码语言 |
C++ |
内存使用 |
24.63 MiB |
提交时间 |
2016-09-02 21:23:54 |
显示代码纯文本
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<algorithm>
#define maxn 500000
using namespace std;
vector<int> G[maxn];
vector<int> g[maxn];
int dp[maxn]={0},s,S,n,m,time=0,D[maxn]={0},d[maxn]={0},tot=0,dt[maxn]={0},low[maxn]={0},mp[maxn]={0};
bool T[maxn]={0},t[maxn]={0},vis[maxn]={0};
queue<int> q;
#define u mp[g[f][i]]
void spfa(){
memset(vis,0,sizeof(vis));
q.push(s);
dp[s]=d[s];
vis[s]=1;
int ans=0;
if (t[s]==1){
ans=dp[s];
}
while(!q.empty()){
int f=q.front();
for (int i=0;i<g[f].size();i++) if(f!=u){
if (dp[u]<dp[f]+d[u]){
dp[u]=dp[f]+d[u];
if (vis[u]==0){
vis[u]=1;
q.push(u);
}
}
}
vis[f]=0;
//printf("%d %d\n",f,dp[f]);
q.pop();
}
for (int i=1;i<=tot;i++){
if (dp[i]>ans&&t[i]==1) ans=dp[i];
//printf("");
}
printf("%d\n",ans);
}
stack<int> st;
void makenode(int x){
tot++;
while(0==st.empty()){
int p=st.top();
mp[p]=tot;
d[tot]+=D[p];
t[tot]=t[tot]|T[p];
for (int i=0;i<G[p].size();i++){
g[tot].push_back(G[p][i]);
//printf(" %d %d\n",tot,G[p][i]);
}
vis[p]=1;
st.pop();
if (dt[x]==dt[p]){
break;
}
}
/*for (int i=0;i<g[tot].size();i++){
printf("%d %d\n",tot,g[tot][i]);
}*/
//printf(" %d\n",t[tot]);
}
void dfs(int x){
if (vis[x]!=0) return;
dt[x]=++time;
low[x]=dt[x];
st.push(x);
for (int i=0;i<G[x].size();i++){
if (low[G[x][i]]==0||low[x]<low[G[x][i]]){
dfs(G[x][i]);
}
if (vis[G[x][i]]==0)low[x]=min(low[x],low[G[x][i]]);
}
// printf("%d %d %d\n",x,dt[x],low[x]);
if (dt[x]==low[x]) makenode(x);
}
void read(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
}
for (int i=1;i<=n;i++){
scanf("%d",&D[i]);
}
int p;
scanf("%d%d",&S,&p);
for (int i=1;i<=p;i++){
int o;
scanf("%d",&o);
T[o]=1;
}
}
int main(){
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
read();
dfs(S);
s=mp[S];
spfa();
/* for (int i=1;i<=tot;i++){
for (int j=0;j<g[i].size();j++){
printf("%d %d\n",i,g[i][j]);
}
printf("\n");
}*/
}