差分约束，对于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()) { PRintf("NIE/n"); return 0; } id=cnt=tp=0; for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) { int bx=belong[i]; for(int j=1;j<=n;j++) if(bx==belong[j]) up(ans[bx],f[i][j]); } int ret=0; for(int i=1;i<=cnt;i++) ret+=ans[i]+1; printf("%d/n",ret); return 0;}新闻热点
疑难解答
