【题解】[NOI2019Route]（70分）

我不是女神ヾ 2021-11-18 01:18 224阅读 0赞

占坑

做法是拆掉所有式子，拆完式子看一下，如果A=0，发现边被分为了终点走向n的边和不走向n的边。所以边就有了新的边权，并且可以相加。然后通过网络流建模的套路建模使得满足时间的限制，然后由于有负边，所以跑spfa，这里60分。然后还有两个点是一条链，送10分。

先放代码，还没测，可能会爆零。交上去的爆零了因为没写freopenQAQ

//@winlere #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ERP(t,a) for(register int t=head[a];t;t=e[t].nx) using namespace std; typedef long long ll; inline int qr(){ register int ret=0,f=0; register char c=getchar(); while(c<48||c>57)f|=c==45,c=getchar(); while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar(); return f?-ret:ret; } namespace sol1{ const int maxn=3e5+5; struct E{ int fr,to,st,ed; E(){to=fr=st=ed=0;} E(const int&a,const int&b,const int&c,const int&d){ fr=a;to=b;st=c;ed=d; } }data[maxn]; ll w[maxn]; int arc[maxn]; int cnt; int nodecnt; typedef pair < ll , int > P; //priority_queue< P , vector<P>,greater <P> > q; queue<P> q; bool in[maxn<<2]; vector < int > fr[maxn],to[maxn]; vector < P > e[maxn<<2]; inline bool cmp(const int&a,const int&b){ return data[a].ed>data[b].ed; } int n,m,A,B,C; inline bool cmp2(const int&a,const int&b){ return data[a].st>data[b].st; } ll d[maxn<<2]; inline ll spfa(){ for(register int t=1;t<maxn<<2;++t) d[t]=2e18; d[0]=0;in[0]=1; q.push(make_pair(0,0)); while(!q.empty()){ P cur=q.front(); q.pop();in[cur.second]=0; for(register int t=0,edd=e[cur.second].size();t<edd;++t){ //cout<<d[e[cur.second][t].second]<<' '<<d[cur.second]+e[cur.second][t].first<<endl; if(d[e[cur.second][t].second]>d[cur.second]+e[cur.second][t].first){ d[e[cur.second][t].second]=d[cur.second]+e[cur.second][t].first; if(!in[e[cur.second][t].second]) q.push(make_pair(d[e[cur.second][t].second],e[cur.second][t].second)),in[e[cur.second][t].second]=1; } } } return d[m+1]; } inline void add(const int&fr,const int&to,const ll&w){ //cout<<"fr="<<fr<<' '<<"to="<<to<<" w="<<w<<endl; e[fr].push_back(make_pair(w,to)); } inline int init(const int&a,const int&b,const int&c,const int&d1,const int&e1){ n=a;m=b;A=c;B=d1;C=e1; nodecnt=n; for(register int t=1,x,y,p,q;t<=m;++t){ x=qr();y=qr();p=qr();q=qr(); //cout<<x<<' '<<y<<' '<<p<<' '<<q<<endl; data[t]=E(x,y,p,q); w[t]=C+1ll*B*p+1ll*A*p*p; if(y!=n) w[t]=w[t]+1ll*A*q*q-1ll*B*q; if(y==n) w[t]=w[t]+0ll+q; fr[x].push_back(t);to[y].push_back(t); if(x==1) add(0,t,w[t]); if(y==n) add(t,m+1,0); } for(register int t=1;t<=n;++t){ //if(fr[t].empty()||to[t].empty())continue; sort(to[t].begin(),to[t].end(),cmp); sort(fr[t].begin(),fr[t].end(),cmp2); int k=0;/* cout<<t<<' '<<fr[t].size()<<' '<<to[t].size()<<endl; cout<<"fr="; for(auto f:fr[t]) cout<<f<<" "; putchar('\n'); cout<<"to="; for(auto f:to[t]) cout<<f<<" "; putchar('\n'); */ for(register int i=0,edd=to[t].size(),ed2=fr[t].size();i<edd;++i){ if(i<edd-1)add(to[t][i+1],to[t][i],0); while(k<ed2&&data[fr[t][k]].st>=data[to[t][i]].ed) add(to[t][i],fr[t][k],w[fr[t][k]]),++k; } } cout<<spfa()<<endl; return 0; } } int main(){ freopen("route.in","r",stdin); freopen("route.out","w",stdout); int a=qr(),b=qr(),c=qr(),d=qr(),e=qr(); if(a<=100&&b==a-1&&c!=0){ ll A=c,B=d,C=e; ll ans=1ll*a*C; ll t1=0,t2=0,t3=0; for(register int t=1;t<=b;++t){ qr();qr();t1=qr();t2=qr(); ans+=B*(t1-t3)+A*(t1-t3)*(t1-t3); t3=t2; } cout<<ans+t3<<endl; return 0; } return sol1::init(a,b,c,d,e); return 0; }

转载于:https://www.cnblogs.com/winlere/p/11195100.html