链接：https://www.nowcoder.com/acm/contest/117/F
来源：牛客网
汤圆防漏理论
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
ghc很喜欢吃汤圆，但是汤圆很容易被粘(zhān)漏。
根据多年吃汤圆经验，ghc总结出了一套汤圆防漏理论：
互相接触的汤圆容易粘(zhān)在一起，并且接触面积不同，粘(zhān)在一起的粘(nián)度也不同。
当ghc要夹起一个汤圆时，这个汤圆和现在碗里与这个汤圆接触的所有汤圆之间的粘(nián)度的和，如果大于汤圆的硬度，这个汤圆就会被粘(zhān)漏。
今天ghc又要煮汤圆啦，今天要煮n个汤圆，并且摆盘的方法已经设计好：
汤圆按照编号，有m对汤圆互相接触，用xi, yi, zi表示编号为xi和yi的两个汤圆互相接触，粘(nián)度为zi。
汤圆当然是越软越好吃，但是ghc的厨艺只允许把所有汤圆煮成同样的硬度。那么，汤圆的硬度最小可以是多少，可以满足吃的过程中，存在一种夹汤圆的顺序，使得没有汤圆会被粘(zhān)漏呢？
注意：
不考虑汤圆的重力作用；
不能同时夹多个汤圆；
吃完汤圆一定要喝点汤。
输入描述:
第一行是一个正整数T(≤ 5)，表示测试数据的组数，
对于每组测试数据，
第一行是两个整数n,m(1≤ n,m≤ 100000)，
接下来m行，每行包含三个整数xi, yi, zi(1≤ xi, yi ≤ n, xi ≠ yi, 1 ≤ zi ≤ 1000000)，
同一对汤圆不会出现两次。
输出描述:
对于每组测试数据，输出一行，包含一个整数，表示汤圆硬度的最小值。
输入例子:
1
4 6
1 2 2
1 3 2
1 4 2
2 3 3
2 4 3
3 4 5
输出例子:
6
-->
法一：直接算
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + ; using LL = long long;
using P = pair<LL, int>; LL cnt[N];
int n, m; set<P> edge[N]; priority_queue<P, vector<P>, greater<P> > Q; void Work()
{
LL ans = ;
for(int i = ; i <= n; i++)
{
Q.push({cnt[i], i});
}
while(!Q.empty())
{
auto tmp = Q.top(); Q.pop();
if(tmp.first != cnt[tmp.second]) continue;
int u = tmp.second;
ans = max(ans, tmp.first);
for(auto p : edge[u])
{
int v = p.second;
cnt[v] -= p.first;
edge[v].erase({p.first, u});
Q.push({cnt[v], v});
}
}
cout << ans << endl;
} int main()
{
int T;
cin >> T;
while(T--)
{
cin >> n >> m;
for(int i = ; i <= n; i++)
{
edge[i].clear();
cnt[i] = ;
} int u, v, w;
for(int i = ; i <= m; i++)
{
cin >> u >> v >> w;
cnt[u] += w;
cnt[v] += w;
edge[u].insert({w, v});
edge[v].insert({w, u});
}
Work();
} }
#include<cstdio>
#include<cmath>
#include<set>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define ll long long
#define N 100000
#define mod 1000000007
#define pa pair<ll,ll>
vector<pa>g[N+];
set<pa>p;
ll sum[N+]; //表示编号为i的人的粘稠度综合
bool vis[N+]; //去重
int main()
{
int i,j,t,q,n,m,a,b,w,x;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=;i<=n;i++) //p不需要清了，本来就是空的
{
g[i].clear();
sum[i]=;
vis[i]=false;
}
while(m--)
{
scanf("%d%d%d",&a,&b,&w);
g[a].push_back(pa(b,w));
g[b].push_back(pa(a,w)); //将a,b连接起来
sum[a]+=w;
sum[b]+=w;
}
for(i=;i<=n;i++)
p.insert(pa(sum[i],i)); //将数据输入到set
ll maxd=;
while(!p.empty()) //贪心
{
set<pa>::iterator it=p.begin();
pa now= *it; //now.first表示他的粘稠度，now,second表士坐标
p.erase(*it);
maxd=max(now.first,maxd);
// printf("%lld now.first=%lld\n",maxd,now.first);
x=now.second;
vis[x]=true; //标记
//第一步，删除权值的边
for(i=;i<g[x].size();i++)
{
pa l=g[x][i]; //为了理解，再写下，l.first是x对应的边
if(vis[l.first])
continue;
p.erase(pa(sum[l.first],l.first));
sum[l.first]-=l.second;
p.insert(pa(sum[l.first],l.first));
} }
printf("%lld\n",maxd);
} return ;
}
题解：
二分硬度，拓扑排序判断是否可行
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+;
struct node
{
int to;ll cost;
};
vector<node>p[maxn];
queue<int>P;
ll a[maxn],zz[maxn];
bool vis[maxn];
int n,m,xx[maxn],yy[maxn];
bool pp(ll x)
{
for(int i=;i<=n;i++)p[i].clear();
memset(a,,sizeof(a));
for(int i=;i<m;i++)
{
node e;e.to=yy[i];e.cost=zz[i];
p[xx[i]].push_back(e);
e.to=xx[i];
p[yy[i]].push_back(e);
a[xx[i]]+=zz[i];
a[yy[i]]+=zz[i];
}
int ans=;memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
if(!vis[i]&&a[i]<=x)
{
ans++;
vis[i]=;
for(int j=;j<p[i].size();j++)
{
int to=p[i][j].to;ll z=p[i][j].cost;
a[to]-=z;
if(!vis[to]&&a[to]<=x)P.push(to),ans++,vis[to]=;
}
}
}
while(!P.empty())
{
int v=P.front();P.pop();
for(int i=;i<p[v].size();i++)
{
node e=p[v][i];
a[e.to]-=e.cost;
if(!vis[e.to]&&a[e.to]<=x)P.push(e.to),ans++,vis[e.to]=;
}
}
if(ans==n)return ;
return ;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=;i<m;i++)
{
int x,y;ll z;
scanf("%d%d%lld",&x,&y,&z);
xx[i]=x;yy[i]=y;zz[i]=z;
}
ll l=-,r=1e18;
while(r-l>)
{
ll mid=(l+r)/;
if(pp(mid))r=mid;
else l=mid;
}
printf("%lld\n",r);
}
return ;
}