社区讨论

floyd寻找路径40pts求助

ccainiaoshanglu
P10080 [GDKOI2024 提高组] 匹配参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lrxl5g8x
此快照首次捕获于
2024/01/28 22:17
2 年前
此快照最后确认于
2024/01/29 09:19
2 年前
查看原帖
rt.考场上写的代码，但是怎么调都过不去。
CPP
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cassert>
#define int long long
using namespace std;

void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x*=f;
}
struct Edge{
	int to,nxt,upl;
	Edge(){}
	Edge(int t,int nx,int u){
		to=t;
		nxt=nx;
		upl=u;
	}
} e[1000010];
int hs[1010],tot=-1,cur[1010];
void add(int u,int v,int w){
	e[++tot]=Edge(v,hs[u],w);
	hs[u]=tot;
}
int dist[1010];
bool bfs(int s,int t){
	memset(dist,0,sizeof(dist));
	queue<int> q;
	q.push(s);
	dist[s]=1;
	while(q.size()){
		int f=q.front();
		q.pop(); 
		cur[f]=hs[f];
		for(int i=hs[f];~i;i=e[i].nxt){
			if(!dist[e[i].to] && e[i].upl){
				dist[e[i].to]=dist[f]+1;
				q.push(e[i].to);
			}
		}
	}
	return dist[t];
}
int dfs(int k,int mx,int t){
	if(k==t || !mx){
		return mx;
	}
	int sum=0;
	for(int &i=cur[k];~i;i=e[i].nxt){
		if(dist[e[i].to]==dist[k]+1 && e[i].upl){
			int tmp=dfs(e[i].to,min(mx-sum,e[i].upl),t);
			if(tmp){
				sum+=tmp;
				e[i].upl-=tmp;
				e[i^1].upl+=tmp;
				if(mx==sum){
					break;
				}
			}else{
				dist[e[i].to]=-1;
			}
		}
	}
	return sum;
}
int getflow(int s,int t){
	int res=0;
	while(bfs(s,t)){
		res+=dfs(s,1e18,t);
	}
	return res;
}
int t,n,m,col[1010];
int pre[2][1010][1010],len[2][1010][1010],tmp[1010];
int is[1010][1010],val[1010][1010];
bool chk[1010];
signed main(){
//	freopen("matching.in","r",stdin);
//	freopen("matching.out","w",stdout);
	read(t);
	while(t--){
		memset(hs,-1,sizeof(hs));
		tot=-1;
		read(n);
		read(m);
		int u,v;
		for(int i=1;i<=2*n;i++){
			for(int j=1;j<=2*n;j++){
				is[i][j]=val[i][j]=0;
				pre[0][i][j]=pre[1][i][j]=0;
				len[0][i][j]=len[1][i][j]=1e18;
			}
		}
		int s=2*n+1,t=2*n+2;
		for(int i=1;i<=m;i++){
			read(u);
			read(v);
			read(col[i]);
			is[u][v]=is[v][u]=i;
			add(u,v,1);
			add(v,u,0);
		}
		for(int i=1;i<=n;i++){
			add(s,i,1);
			add(i,s,0);
			add(i+n,t,1);
			add(t,i+n,0);
		}
		int f=getflow(s,t);
		if(f!=n){
			printf("-1\n");
			continue;
		}
		for(int i=1;i<=n;i++){
			for(int j=hs[i];~j;j=e[j].nxt){
				if(e[j].upl==0){
					cur[i]=e[j].to;
				}
			}
		}
		int sum=0;
		for(int i=1;i<=n;i++){
			sum+=col[is[i][cur[i]]];
		}
		if(sum%2==0){
			for(int i=1;i<=n;i++){
				printf("%lld ",is[i][cur[i]]);
			}
			putchar('\n');
		}else{
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(i!=j && is[cur[i]][j]){
						pre[col[is[cur[i]][j]]^col[is[i][cur[i]]]][i][j]=i;
						len[col[is[cur[i]][j]]^col[is[i][cur[i]]]][i][j]=1;
						val[i][j]=col[is[cur[i]][j]]^col[is[i][cur[i]]];
					}
				}
			}
			for(int k=1;k<=n;k++){
				for(int i=1;i<=n;i++){
					for(int j=1;j<=n;j++){
						for(int p=0;p<=1;p++){
							for(int q=0;q<=1;q++){
								if(pre[p][i][k] && pre[q][k][j]){
									if(len[p][i][k]+len[q][k][j]<len[p^q][i][j]){
										pre[p^q][i][j]=pre[q][k][j];
										len[p^q][i][j]=len[p][i][k]+len[q][k][j];
									}
								}
							}
						}
					}
				}
			}
			for(int i=1;i<=n;i++){
				tmp[i]=cur[i];
			}
			for(int i=1;i<=n;i++){
				if(pre[1][i][i]){
					for(int j=1;j<=2*n;j++){
						chk[j]=0;
					}
					int lst=i,pos=pre[1][i][i],opt=1;
					while(1){
						if(chk[pos]){
							goto live;
						}
						chk[pos]=1;
						opt^=val[pos][lst];
						lst=pos;
						pos=pre[opt][i][pos];
						if(lst==i){
							break;
						}
					}
					lst=i,pos=pre[1][i][i],opt=1;
					while(1){
						cur[lst]=tmp[pos];
						opt^=val[pos][lst];
						lst=pos;
						pos=pre[opt][i][pos];
						if(lst==i){
							break;
						}
					}
					for(int i=1;i<=n;i++){
						printf("%lld ",is[i][cur[i]]);
					}
					putchar('\n');
					goto die;
					live:;
				}
			}
			printf("-1\n");
			die:;
		}
	}
	return 0;
}
另外，我赛后还写了一版dfs的，貌似也只有40pts。 求助/kk
CPP
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cassert>
#define int long long
using namespace std;

void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x*=f;
}
struct Edge{
	int to,nxt,upl;
	Edge(){}
	Edge(int t,int nx,int u){
		to=t;
		nxt=nx;
		upl=u;
	}
} e[2000010];
int hs[1010],tot=-1,cur[1010];
void add(int u,int v,int w){
	e[++tot]=Edge(v,hs[u],w);
	hs[u]=tot;
}
int dist[1010];
bool bfs(int s,int t){
	memset(dist,0,sizeof(dist));
	queue<int> q;
	q.push(s);
	dist[s]=1;
	while(q.size()){
		int f=q.front();
		q.pop(); 
		cur[f]=hs[f];
		for(int i=hs[f];~i;i=e[i].nxt){
			if(!dist[e[i].to] && e[i].upl){
				dist[e[i].to]=dist[f]+1;
				q.push(e[i].to);
			}
		}
	}
	return dist[t];
}
int dfs(int k,int mx,int t){
	if(k==t || !mx){
		return mx;
	}
	int sum=0;
	for(int &i=cur[k];~i;i=e[i].nxt){
		if(dist[e[i].to]==dist[k]+1 && e[i].upl){
			int tmp=dfs(e[i].to,min(mx-sum,e[i].upl),t);
			if(tmp){
				sum+=tmp;
				e[i].upl-=tmp;
				e[i^1].upl+=tmp;
				if(mx==sum){
					break;
				}
			}else{
				dist[e[i].to]=-1;
			}
		}
	}
	return sum;
}
int getflow(int s,int t){
	int res=0;
	while(bfs(s,t)){
		res+=dfs(s,1e18,t);
	}
	return res;
}
int t,n,m,col[1010];
int tmp[1010];
int is[1010][1010],val[1010][1010];
int stk[10010],tp=0,cyc[10010];
bool vis[1010],instk[1010];
vector<int> eq[1010];
bool dfs(int k){
	if(instk[k^1]){
		for(int i=1;i<=n;i++){
			tmp[i]=cur[i];
		}
		int cnt=0;
		while(stk[tp-cnt]!=(k^1)){
			int p=stk[tp-cnt];
			cyc[++cnt]=p;
		}
		cyc[++cnt]=k;
		for(int i=1;i<=cnt;i++){
			cur[cyc[i]/2]=tmp[cyc[i%cnt+1]/2];
		}
		for(int i=1;i<=n;i++){
			printf("%lld ",is[i][cur[i]]);
		}
		return 1;
	}
	instk[stk[++tp]=k]=1;
	vis[k]=1;
	for(int i:eq[k]){
		if(!vis[i]){
			if(dfs(i)){
				return 1;
			}
		}
	}
	tp--;
	instk[k]=0;
	return 0;
}
signed main(){
//	freopen("matching.in","r",stdin);
//	freopen("matching.out","w",stdout);
	read(t);
	while(t--){
		memset(hs,-1,sizeof(hs));
		tot=-1;
		read(n);
		read(m);
		int u,v;
		for(int i=1;i<=2*n;i++){
			for(int j=1;j<=2*n;j++){
				is[i][j]=0;
			}
		}
		int s=2*n+1,t=2*n+2;
		for(int i=1;i<=m;i++){
			read(u);
			read(v);
			read(col[i]);
			is[u][v]=is[v][u]=i;
			add(u,v,1);
			add(v,u,0);
		}
		for(int i=1;i<=n;i++){
			add(s,i,1);
			add(i,s,0);
			add(i+n,t,1);
			add(t,i+n,0);
		}
		int f=getflow(s,t);
		if(f!=n){
			printf("-1\n");
			continue;
		}
		for(int i=1;i<=n;i++){
			for(int j=hs[i];~j;j=e[j].nxt){
				if(e[j].upl==0){
					cur[i]=e[j].to;
				}
			}
		}
		int sum=0;
		for(int i=1;i<=n;i++){
			sum+=col[is[i][cur[i]]];
		}
		if(sum%2==0){
			for(int i=1;i<=n;i++){
				printf("%lld ",is[i][cur[i]]);
			}
			putchar('\n');
		}else{
			for(int i=1;i<=2*n+1;i++){
				eq[i].clear();
			}
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(i!=j && is[cur[i]][j]){
						if(col[is[cur[i]][j]]^col[is[i][cur[i]]]){
							eq[i*2].push_back(j*2+1);
							eq[i*2+1].push_back(j*2);
						}else{
							eq[i*2].push_back(j*2);
							eq[i*2+1].push_back(j*2+1);
						}
					}
				}
			}
			for(int i=1;i<=n;i++){
				memset(vis,0,sizeof(vis));
				memset(instk,0,sizeof(instk));
				tp=0;
				if(dfs(i*2)){
					putchar('\n');
					goto die;
				}
			}
			printf("-1\n");
			die:;
		}
	}
	return 0;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...