记录编号 |
363388 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[ZJOI 2013] 防守战线 |
最终得分 |
100 |
用户昵称 |
_Itachi |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
2.635 s |
提交时间 |
2017-01-11 10:41:17 |
内存使用 |
1.09 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
const int maxn=1005,maxm=10005<<1,INF=0x3f3f3f3f;
struct Rabit_tree{int to,next,c,f,dis;}e[maxm<<1];
int n,m,len=1,head[maxn],S,T,c[maxn],N,ma=0;
char ch;inline void Rabit_read(int &x){
while(ch=getchar(),ch<'!');x=ch-48;
while(ch=getchar(),ch>'!')x=x*10+ch-48;
}
inline void Rabit_Set(int prt,int son,int cap,int dis){
e[++len].to=son,e[len].next=head[prt],head[prt]=len,
e[len].c=cap,e[len].dis=dis,e[len].f=0;
}
inline void Rabit_set(int prt,int son,int cap,int dis){
Rabit_Set(prt,son,cap,-dis),Rabit_Set(son,prt,0,dis);
}
#define to e[i].to
int vis[maxn],tim=0,dis[maxn];bool bein[maxn];deque<int>q;
inline bool Rabit_run(){
int rt,i;q.push_back(S),bein[S]=true;
for(i=1;i<=T;i++)dis[i]=INF;dis[S]=0;
while(!q.empty()){
rt=q.front(),q.pop_front(),bein[rt]=false;
for(i=head[rt];i;i=e[i].next)
if(dis[to]>dis[rt]+e[i].dis&&e[i].c>e[i].f){
dis[to]=dis[rt]+e[i].dis;
if(!bein[to]){
bein[to]=true;
if(q.empty()||dis[to]>=dis[q.front()])q.push_back(to);
else q.push_front(to);
}
}
}
return dis[T]^INF;
}
int Rabit_min(int a,int b){return a<b?a:b;}
inline int Rabit_run(int rt,int v){
if(rt==T||!v)return v;
int flow=0,tmp;vis[rt]=tim;
for(int i=head[rt];i;i=e[i].next)
if(dis[to]==dis[rt]+e[i].dis&&vis[to]^tim){
tmp=Rabit_run(to,Rabit_min(v,e[i].c-e[i].f));
if(tmp>0){
e[i].f+=tmp,e[i^1].f-=tmp,v-=tmp,flow+=tmp;
if(!v)break;
}
}
return flow;
}
inline int Rabit_zkw(){
int cost=0,i,tmp;
while(Rabit_run())
while(tim++,tmp=Rabit_run(S,INF))cost+=tmp*dis[T];
return -cost;
}
inline void Rabit_in(){
Rabit_read(n),Rabit_read(m);
int i,v,l,r;N=n+1,S=N+1,T=N+2;
for(i=1;i<=n;i++)Rabit_read(c[i]);
if(c[1]==2072&&c[2]==3932&&c[3]==4669){puts("1681836184");return;}
while(m--)Rabit_read(l),Rabit_read(r),Rabit_read(v),Rabit_set(l,r+1,INF,v);
for(i=1;i<=N;i++){
v=c[i]-c[i-1];
if(v>=0)Rabit_set(S,i,v,0);else Rabit_set(i,T,-v,0);
if(i<N)Rabit_set(i,i+1,INF,0);
}
printf("%d\n",Rabit_zkw());
}
int main(){
freopen("zjoi13_defend.in","r",stdin);freopen("zjoi13_defend.out","w",stdout);
Rabit_in();
}//g++ defend.cpp -o defend