差分約束，對于Xa+1=Xb這樣的限制連正向反向兩條邊限制 跑一次Floyd，有負環則無解 然后tarjan縮點，不同聯通分量答案互不影響，對于一個聯通分量，他的答案數是最遠點對之間的最短距離+1，然后加起來
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long longusing namespace std;void up(int &x,int y){if(x<y)x=y;}void down(int &x,int y){if(x>y)x=y;}const int maxn = 610;const int maxm = 110000;struct edge{ int y,nex; edge(){} edge(int _y,int _nex){y=_y;nex=_nex;}}a[maxm<<1]; int len,fir[maxn];int n,m1,m2,f[maxn][maxn];void ins(int x,int y){ a[++len]=edge(y,fir[x]); fir[x]=len;}void Floyd(){ for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) down(f[i][j],f[i][k]+f[k][j]); }}bool judge(){ Floyd(); for(int i=1;i<=n;i++) if(f[i][i]!=0) return false; return true;}int dfn[maxn],low[maxn],id;int cnt,belong[maxn];int sta[maxn],tp;bool v[maxn];void tarjan(int x){ dfn[x]=low[x]=++id; v[x]=true; sta[++tp]=x; for(int k=fir[x];k;k=a[k].nex) { int y=a[k].y; if(!dfn[y]) { tarjan(y); down(low[x],low[y]); } else if(v[y])down(low[x],dfn[y]); } if(dfn[x]==low[x]) { cnt++; int la=0; while(la!=x) { la=sta[tp--]; belong[la]=cnt; v[la]=false; } }}int ans[maxn];int main(){ memset(f,63,sizeof f); scanf("%d%d%d",&n,&m1,&m2); for(int i=1;i<=n;i++) f[i][i]=0; for(int i=1;i<=m1;i++) { int x,y; scanf("%d%d",&x,&y); down(f[x][y],1); down(f[y][x],-1); ins(x,y); ins(y,x); } for(int i=1;i<=m2;i++) { int x,y; scanf("%d%d",&x,&y); down(f[y][x],0); ins(y,x); } if(!judge()) {新聞熱點
疑難解答
