【JZOJ3640】【COCI2014】utrka

2019-11-06 06:03:59

字體：大中小

供稿：網(wǎng)友

Mission

這里寫圖片描述 2<=N<=300,2<=M<=N?(N?1) $2<=N<=300,2<=M<=N*(N-1)$

Solution

SPFA。由于只是二元關(guān)系，所以條件隨便寫。具體來說，如果是u?v $u?v$ 。若v $v$ 的最大領(lǐng)先時(shí)間還不是正數(shù)，就要使得v $v$ 的最大領(lǐng)先時(shí)間盡量大；若v $v$ 的最大領(lǐng)先時(shí)間已經(jīng)是正數(shù)，就要使得v $v$ 的經(jīng)過道路盡量少；

Code

#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<math.h>#define ll long longusing namespace std;const char* fin="utrka.in";const char* fout="utrka.out";const int inf=0x7fffffff;const int maxn=307,maxm=maxn*maxn;int n,m,i,j,k,l,o,ans1=inf,ans2=0;int fi[maxn],ne[maxm],la[maxm],va[maxm],tot;int head,tail,b[maxm*10],dis[maxn],val[maxn];bool bz[maxn];void add_line(int a,int b,int c){ tot++; ne[tot]=fi[a]; la[tot]=b; va[tot]=c; fi[a]=tot;}void add(int v,int Dis,int Val){ if (val[v]<=0 && (val[v]<Val || val[v]==Val && dis[v]>Dis) || val[v]>0 && (dis[v]>Dis || dis[v]==Dis && val[v]<Val)){ dis[v]=Dis; val[v]=Val; if (!bz[v]){ bz[v]=true; b[++tail]=v; } }}void spfa(int st){ int i,j,k; memset(dis,127,sizeof(dis)); memset(val,128,sizeof(val)); head=tail=0; add(st,0,0); while (head++<tail){ for (k=fi[b[head]];k;k=ne[k]) if (la[k]==st){ if (val[b[head]]+va[k]>0){ if (ans1>dis[b[head]]+1){ ans1=dis[b[head]]+1; ans2=val[b[head]]+va[k]; }else if (ans1==dis[b[head]]+1) ans2=min(ans2,val[b[head]]+va[k]); } }else add(la[k],dis[b[head]]+1,val[b[head]]+va[k]); bz[b[head]]=false; }}int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%d%d",&n,&m); for (i=1;i<=m;i++){ scanf("%d%d%d%d",&j,&k,&l,&o); add_line(j,k,o-l); } for (i=1;i<=n;i++) spfa(i); Warning

比賽的時(shí)候也想到是這樣，但沒敢打。T T 其實(shí)以前l(fā)ilypad，已經(jīng)是這樣了。