差分约束建图，发现要在每个联通块里求最长路，600，直接O(n3) floyed
#include#include #include #include #include #define N 650#define M 100050using namespace std;int g[N][N],n,m1,m2,f[N],ans;int e=1,head[N];struct edge{ int u,v,w,next;}ed[2*M];void add(int u,int v,int w){ ed[e].u=u;ed[e].v=v;ed[e].w=w; ed[e].next=head[u];head[u]=e++; g[u][v]=min(g[u][v],w);}int dfn[N],low[N],top,q[N],tot,id[N];bool bo[N];void tarjan(int x){ dfn[x]=low[x]=++top; q[top]=x;bo[x]=1; for(int i=head[x];i;i=ed[i].next){ int v=ed[i].v; if(!dfn[v]){ tarjan(v); low[x]=min(low[x],low[v]); } else if(bo[v]) low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]){ int y;tot++; do{ y=q[top--]; bo[y]=0; id[y]=tot; }while(y!=x); }}int main(){ memset(g,0x3f,sizeof g); scanf("%d%d%d",&n,&m1,&m2); for(int i=1;i<=n;i++)g[i][i]=0; int u,v; for(int i=1;i<=m1;i++){ scanf("%d%d",&u,&v); add(u,v,1);add(v,u,-1); } for(int i=1;i<=m2;i++){ scanf("%d%d",&u,&v); add(v,u,0); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++)if(id[i]==id[k]) for(int j=1;j<=n;j++)if(id[j]==id[i]) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); for(int i=1;i<=n;i++) if(g[i][i]<0){printf("NIE\n");return 0;} for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(id[i]==id[j]) f[id[i]]=max(f[id[i]],g[i][j]+1); for(int i=1;i<=tot;i++) ans+=f[i]; printf("%d\n",ans); return 0;}