WA了#18 hack点 求调
查看原帖
WA了#18 hack点 求调
1011779
wangyichen_0711楼主2025/8/4 20:16
#include <bits/stdc++.h>
#define int  double
#define x first
#define y second
using namespace std;
inline int read(){//快读 
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
pair<int,short>a[100100];//存储每一点的a+bx 中的a和b 
vector<pair<int,int> >b[100100];//存边 
int n,m;//点数 边数 
double ans[100100],xx=0;//每个点的值  每个连通块的x部分解 
bool vis[100100];//是否遍历过点i 
	long long u,v,d;
bool solve(long long t){//起点为t的连通块部分解 
//	if(m<n){
//		cout<<"IMPOSSIBLE";
//		return 0;
//	}	
	xx=0;
	a[t].x=0,a[t].y=1;
	queue<int>q;
	q.push(t);
	vis[t]=1;//初始化 
	while(!q.empty()){
		u=q.front();
		q.pop();
		for(int i=0;i<b[u].size();i++){
			v=b[u][i].x,d=b[u][i].y;
//			cout<<u<<" "<<v<<" "<<d<<" "<<a[v].x<<" "<<a[v].y<<endl;
			if(a[v].x!=0&&a[v].y!=0){//系数和为0时 
				double xxx=0;
				if(a[u].y+a[v].y==0){
					if(a[u].x+a[v].x!=d){
						cout<<"IMPOSSIBLE";
						return 0;
					}
				}
				else if(a[u].y+a[v].y==2){//系数和为2时 
					xxx=(d-a[u].x-a[v].x)/2;
					if(xx!=0&&xxx!=xx){
						cout<<"IMPOSSIBLE";
						return 0;
					}
					xx=xxx;
				}
				else{//系数和为-2时 
					xxx=(a[u].x+a[v].x-d)/2;
					if(xx!=0&&xxx!=xx){
						cout<<"IMPOSSIBLE";
						return 0;
					}
					xx=xxx;
				}
			}
			else{//没有访问过边i 
				if(vis[v])continue;
				vis[v]=1;
				pair<int,int> yyy;
				yyy.x=d-a[u].x,yyy.y=-1*a[u].y;
				a[v]={yyy};
				q.push(v);
			}
		}
	}
	for(long long i=1;i<=n;i++){//计算部分答案 
		if(vis[i]&&!ans[i]){
			ans[i]=a[i].x+a[i].y*xx;
		}		
	}
	return 1;
}
signed main(){
	n=read(),m=read();
	for(long long i=1;i<=m;i++){
		u=read(),v=read(),d=read();
		b[u].push_back({v,d});
		b[v].push_back({u,d});
	}
	for(long long i=1;i<=n;i++){
		if(!vis[i]){
			bool c=solve(i);
			if(!c)return 0;
		}
	}
	for(long long i=1;i<=n;i++)
		if(ans[i]<0){
			cout<<"IMPOSSIBLE";
			return 0;
		}
	for(long long i=1;i<=n;i++)printf("%.2f\n",ans[i]);
	return 0;
}
2025/8/4 20:16
加载中...