QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408997 | #7762. 数据库 | kkkgjyismine4 | 0 | 0ms | 0kb | C++14 | 2.2kb | 2024-05-11 14:42:49 | 2024-05-11 14:42:49 |
answer
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int h[10005],w[260000],to[260000],nxt[260000],dis[10005],dis1[10005],f[10005],lst[10005],k,s,t,n,m,cnt;
int rot[10005],p[260000],c[260000],x,y,ans,mx;
bool bl[10005];
void jb(int u,int v,int W,int C){
++cnt;w[cnt]=W;c[cnt]=C;
to[cnt]=v;nxt[cnt]=h[u];h[u]=cnt;
}
void JB(int u,int v,int W,int C){
jb(u,v,W,C);jb(v,u,0,-C);
}
queue<int>q;
bool spfa(){
for(int i=1;i<=k;i++) bl[i]=lst[i]=f[i]=0,dis[i]=inf;
dis[s]=0,f[s]=inf;q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
bl[u]=0;
for(int i=h[u];i!=0;i=nxt[i]){
int v=to[i];
if(w[i]>0&&dis[v]>dis[u]+c[i]){
lst[v]=i;
f[v]=min(f[u],w[i]);
dis[v]=dis[u]+c[i];
if(bl[v]==0){
bl[v]=1;
q.push(v);
}
}
}
}
return lst[t]!=0;
}
#define pii pair<int,int>
#define fi first
#define se second
priority_queue<pii>pq;
int mk[10050];
bool dj(){
for(int i=1;i<=k;i++)bl[i]=lst[i]=f[i]=mk[i]=0,dis[i]=inf;
dis[s]=0,f[s]=inf,pq.push(make_pair(-dis[s],s));
while(pq.size()){
pii dog=pq.top();pq.pop();int u=dog.se;
if(mk[u])continue;mk[u]=1;
for(int i=h[u];i!=0;i=nxt[i]){
int v=to[i];
assert(c[i]+dis1[u]-dis1[v]>=0);
if(w[i]>0&&dis[v]>dis[u]+c[i]+dis1[u]-dis1[v]){
lst[v]=i;
f[v]=min(f[u],w[i]);
dis[v]=dis[u]+c[i]+dis1[u]-dis1[v];
pq.push(make_pair(-dis[v],v));
}
}
}dis[t]+=dis1[t];
return lst[t]!=0;
}
int work(){
bool fl=spfa();
for(int i=1;i<=k;++i)dis1[i]=dis[i];
int mncst=0;
while(dj()==1){
mncst+=dis[t]*f[t];
for(int i=t;i!=s;i=to[lst[i]^1]){
w[lst[i]]-=f[t];
w[lst[i]^1]+=f[t];
}
}
return mncst;
}
int N,M,Q;
int Wc[5500],Id[5050],Lst[5050],stk[5050],tail;
int main(){
cnt=1;
cin>>N>>M>>Q;
for(int i=1;i<=N;++i)scanf("%d",&Wc[i]);int ans1=0;
for(int i=1;i<=Q;++i){
scanf("%d",&Id[i]),ans1+=Wc[Id[i]];
if(tail&&stk[tail]==Id[i])ans1-=Wc[Id[i]];
else stk[++tail]=Id[i];
}
Q=tail;for(int i=1;i<=Q;++i)Id[i]=stk[i];
k=t=Q+2,s=Q+1,t=Q+2;int lst1=s;
for(int i=1;i<=Q;++i)JB(lst1,i,M-1,0),lst1=i;
JB(lst1,t,M-1,0);
for(int i=1;i<=Q;++i){
if(Lst[Id[i]])JB(Lst[Id[i]]+1,i,1,-Wc[Id[i]]);
Lst[Id[i]]=i;
}
int ans=work();
printf("%d",ans+ans1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
10 3 5000 23077 34848 88221 8067 83132 62621 41320 69146 32971 27594 2 7 5 3 9 6 1 9 4 8 1 8 8 3 6 9 1 7 5 5 6 8 1 3 10 6 8 7 10 2 1 2 6 7 5 5 9 5 7 10 10 6 6 7 2 4 3 1 10 10 5 1 1 6 1 2 8 9 2 5 10 1 10 7 5 5 10 5 2 5 6 10 9 5 6 3 5 3 6 5 7 4 1 5 8 1 1 9 7 1 1 2 1 8 6 2 9 8 4 2 5 4 5 2 10 4 3 6 9 7 ...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #4:
score: 0
Runtime Error
input:
10 2 5000 65644 5214 85000 40719 98071 56616 35404 16019 96748 89032 5 9 6 1 3 6 8 10 2 9 1 10 5 9 9 9 2 7 7 7 7 10 5 1 3 10 4 2 5 5 2 8 3 2 1 3 3 6 2 4 5 5 2 5 2 3 4 2 10 1 4 6 10 9 6 4 9 10 5 3 9 7 7 2 1 9 5 8 8 4 8 8 4 5 6 1 3 4 8 10 4 3 6 6 9 2 5 2 8 5 10 4 7 10 3 9 3 2 9 3 10 7 1 3 9 9 3 5 1 3 ...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #7:
score: 0
Runtime Error
input:
5000 15 400 34145 93322 29976 7963 53362 50640 10859 94528 13329 49980 18826 50286 60155 79748 73253 18329 5216 83079 48220 98825 46592 76855 14037 19859 80960 4461 377 70496 28092 99806 5355 27013 92051 95231 65553 32365 3862 89764 86063 93033 12754 68996 38965 52942 69948 34370 3023 52079 16066 57...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #10:
score: 0
Runtime Error
input:
10 5 1000 86764 81108 88408 93029 87155 18790 28170 29349 81866 77109 8 7 10 7 2 7 1 8 4 10 9 10 4 1 7 1 9 9 1 6 6 1 9 6 7 1 8 10 1 7 9 1 1 9 7 10 8 5 5 1 2 3 10 6 2 6 2 6 1 2 7 8 5 6 10 2 9 8 2 6 8 5 10 8 1 10 4 6 5 6 3 8 1 3 5 2 2 7 2 4 5 5 8 2 4 1 3 6 8 2 2 3 1 8 1 5 8 6 9 7 7 3 7 9 8 9 9 7 5 3 6...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%