Portal

 

Analysis

Do the shortest circuit from point s, and then if one edge satisfies dis[i] + w[i][j] = dis[j], we can connect this edge, so that the shortest circuit is to reach point t. To meet the disjoint limit, the capacity of the edge is set to 1.

 

Originally it was just a simple board problem, but it took me more than an hour????

1. The data range is too large (but it's not MLE, it's Segmentation Fault)
2. Naive thought the distance between oneself and oneself was 0 when inputting, the result You can have your own ring

 

Code

#include<bits/stdc++.h>
#define in read()
#define M 400000
#define inf 5000000
#define N 109
using namespace std;
inline int read(){
	char ch;int f=1,res=0;
	while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return f==1?res:-res;
}
int n,S,T;
int f[105][105],g[105][105];
int nxt[M],to[M],cap[M],head[N],cur[N],cnt=1,lev[N];
void add(int x,int y,int z){
	nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;cap[cnt]=z;
	nxt[++cnt]=head[y];head[y]=cnt;to[cnt]=x;cap[cnt]=0;
}
bool bfs(){
	for(int i=1;i<=n;++i){	cur[i]=head[i];lev[i]=-1;} 
	queue<int > q;
	q.push(S);lev[S]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int e=head[u];e;e=nxt[e]){
			int v=to[e];
			if(lev[v]!=-1||cap[e]<=0) continue;
			lev[v]=lev[u]+1;
			if(v==T) return true;
			q.push(v);
 		}
	}
	return false;
}
int dinic(int u,int flow){
	if(u==T)	return flow;
	int delta,res=0;
	for(int &e=cur[u];e;e=nxt[e]){
		int v=to[e];
		if(lev[v]>lev[u]&&cap[e]>0){
			delta=dinic(v,min(cap[e],flow-res));
			if(delta){
				res+=delta;cap[e]-=delta;
				cap[e^1]+=delta;if(res==flow) return flow;
			}
		}
	}
	return res;
}
int main(){
	while(scanf("%d",&n)!=EOF){
		cnt=1;
		memset(head,0,sizeof(head));
		int i,j,k;
		for(i=1;i<=n;++i)
		{
			for(j=1;j<=n;++j){
				g[i][j]=f[i][j]=in;
				if(f[i][j]==-1) g[i][j]=f[i][j]=inf;
			}
			f[i][i]=0;//It's here. It's poisonous 
		}
		S=in;T=in;
		if(S==T) {
			printf("inf\n");
			continue;
		}
		S++;T++;
		for(k=1;k<=n;++k)
			for(i=1;i<=n;++i)
				for(j=1;j<=n;++j)
					if(f[i][k]+f[k][j]<f[i][j])
						f[i][j]=f[i][k]+f[k][j];
		for(i=1;i<=n;++i)
			for(j=1;j<=n;++j){
				if(i==j) continue;
				if(g[i][j]!=inf&&f[S][j]!=inf&&f[S][i]!=inf&&f[S][j]==f[S][i]+g[i][j])
					add(i,j,1);	
			}	
		int maxflow=0;
		while(bfs()) maxflow+=dinic(S,inf);
		printf("%d\n",maxflow);
	}
	return 0;
}