题目链接
368. 银河
银河中的恒星浩如烟海,但是我们只关注那些最亮的恒星。
我们用一个正整数来表示恒星的亮度,数值越大则恒星就越亮,恒星的亮度最暗是 \(1\)。
现在对于 \(N\) 颗我们关注的恒星,有 \(M\) 对亮度之间的相对关系已经判明。
你的任务就是求出这 \(N\) 颗恒星的亮度值总和至少有多大。
输入格式
第一行给出两个整数 \(N\) 和 \(M\)。
之后 \(M\) 行,每行三个整数 \(T, A, B\),表示一对恒星 \((A, B)\) 之间的亮度关系。恒星的编号从 \(1\) 开始。
如果 \(T = 1\),说明 \(A\) 和 \(B\) 亮度相等。
如果 \(T = 2\),说明 \(A\) 的亮度小于 \(B\) 的亮度。
如果 \(T = 3\),说明 \(A\) 的亮度不小于 \(B\) 的亮度。
如果 \(T = 4\),说明 \(A\) 的亮度大于 \(B\) 的亮度。
如果 \(T = 5\),说明 \(A\) 的亮度不大于 \(B\) 的亮度。
输出格式
输出一个整数表示结果。
若无解,则输出 \(-1\)。
数据范围
\(N \le 100000,M \le 100000\)
输入样例:
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
输出样例:
11
解题思路
缩点
同 1169. 糖果,但本题差分约束被卡了,不妨考虑缩点,显然要求强连通分量中的所有边的权值都为 \(0\),否则说明有矛盾,缩完点后便是是一个有向无环图,按照拓扑序递推即可
- 时间复杂度:\(O(n+m)\)
代码
// Problem: 银河
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/370/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=1e5+5;
int n,m;
vector<PII> adj[2][N];
int dfn[N],low[N],timestamp,scc_cnt,id[N],sz[N],stk[N],top;
bool in_stk[N];
int d[N];
void tarjan(int x)
{
dfn[x]=low[x]=++timestamp;
stk[++top]=x,in_stk[x]=true;
for(auto t:adj[0][x])
{
int y=t.fi;
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(in_stk[y])low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
int y;
scc_cnt++;
do
{
y=stk[top--];
in_stk[y]=false;
id[y]=scc_cnt;
sz[scc_cnt]++;
}while(y!=x);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int t,a,b;
scanf("%d%d%d",&t,&a,&b);
if(t==1)
adj[0][a].pb({b,0}),adj[0][b].pb({a,0});
else if(t==2)
adj[0][a].pb({b,1});
else if(t==3)
adj[0][b].pb({a,0});
else if(t==4)
adj[0][b].pb({a,1});
else
adj[0][a].pb({b,0});
}
for(int i=1;i<=n;i++)adj[0][0].pb({i,1});
tarjan(0);
bool f=true;
for(int i=0;i<=n;i++)
for(auto t:adj[0][i])
{
int x=id[i],y=id[t.fi];
if(x==y&&t.se)
{
f=false;
break;
}
adj[1][x].pb({y,t.se});
}
if(!f)
{
puts("-1");
return 0;
}
for(int i=scc_cnt;i>=1;i--)
for(auto t:adj[1][i])
d[t.fi]=max(d[t.fi],d[i]+t.se);
LL res=0;
for(int i=1;i<=scc_cnt;i++)res+=(LL)d[i]*sz[i];
printf("%lld",res);
return 0;
}
原文地址:http://www.cnblogs.com/zyyun/p/16900706.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性