差分约束+vector存图85分,蒟蒻求助还有什么注意的地方吗?
查看原帖
差分约束+vector存图85分,蒟蒻求助还有什么注意的地方吗?
157752
yxr_楼主2020/9/6 16:50
#include<bits/stdc++.h>
using namespace std;

int n,m;
int d[1020000];
bool vis[102000];
int cnt[102000];
bool flag;

queue<int> q;

vector<pair<int,int> > v[102000];

void add(int x,int y,int z) {
	v[x].push_back(make_pair(y,z));
}

int main() {
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		int x,y,z,opt;
//		cin>>x>>y>>z;
//		add(x,y,z);
		cin>>opt;
		/*if(opt==1) {
			cin>>x>>y>>z;
			add(y,x,z);
		} else if(opt==2) {
			cin>>x>>y>>z;
			add(x,y,z);
		} else if(opt==3) {
			cin>>x>>y;
			add(x,y,0);
			add(y,x,0);
		}*/
		if(opt==1) {
			cin>>x>>y>>z;
			add(x,y,-z);
		} else if(opt==2) {
			cin>>x>>y>>z;
			add(y,x,z);
		} else if(opt==3) {
			cin>>x>>y;
			add(x,y,0);
			add(y,x,0);
		}
	}
	
	for(int i=1;i<=n;i++) add(0,i,0);

	int s=1;
	memset(d,0x3f,sizeof(d));

	d[s]=0;
	q.push(s);
	vis[s]=1;

	while(!q.empty() ) {
		int x=q.front() ;
		q.pop() ;
		vis[x]=0;

		for(int i=0; i<v[x].size() ; i++) {
			int y=v[x][i].first;
			int w=v[x][i].second;

			if(d[y]>d[x]+w) {
				d[y]=d[x]+w;
				if(!vis[y]) {
					vis[y]=1;
					q.push(y);
					cnt[y]++;
					if(cnt[y]>n) {
						flag=1;
						break;
					}
				}
			}
		}

		if(flag) break;

	}

	if(flag) cout<<"No"<<endl;

	else {
		for(int i=1; i<=n; i++) {
			if(!vis[i]) {
				cout<<"No"<<endl;
				return 0;
			}
		}
		cout<<"Yes"<<endl;
	}


	return 0;

}
2020/9/6 16:50
加载中...