听微微tingvv,饿狼夫君饱娘子,俄官方禁用微信
思路：注意，行数是无限的，因此，两个人可以同时都相距另一个人x远（相距x列， 不在同一行），也就是说， 出现矛盾的唯一地方就是在于， 现在说的两个人相距的距离和之前说的矛盾。 那么怎么判断矛盾呢， 由于每个人之间有间接关联性，因此，我们需要处理一个集合的距离问题 ， 所以用带权并查集就可以很好的处理。
细节参见代码：
我要评论
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 50000 + 10;
int T,n,m,p[maxn],dist[maxn];
void init(int n) {
for(int i = 1; i <= n; i++) {
p[i] = i;
dist[i] = 0;
}
}
int _find(int x) {
if(p[x] == x) return p[x];
int fa = p[x];
p[x] = _find(p[x]);
dist[x] += dist[fa]; // 路径压缩的时候顺便维护每个点到祖先的距离
return p[x];
}
inline bool BIN(int a, int b, int c) {
int x = _find(a);
int y = _find(b);
if(x == y) {
if(dist[a] + c != dist[b]) return false; // 判断是否矛盾
return true;
}
p[y] = x;
dist[y] = dist[a] - dist[b] + c; // 计算相对距离， a和b相距c， 那么根据向量加减， 可以求出dist[y]。具体可以画个图看看
return true;
}
int a, b, c;
int main() {
while(~scanf("%d%d",&n,&m)) {
init(n);
int ans = 0;
while(m--) {
scanf("%d%d%d",&a,&b,&c);
if(!BIN(a, b, c)) ++ans;
}
printf("%d\n",ans);
}
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论