分析:
可以通过差分约束系统来做,通过spfa判正环,每个节点的最短路即为亮度。但本题数据上过不去。
正解:tarjan算法求图的强连通分量,只要分量中存在一个边权非0的点,即表示无解(同一一个分量中存在环,因此每个节点的亮度必相同)。若有解则进行缩点,得到一个DAG图,通过topo排序即可得到每个节点的亮度。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Edge{ int ver,next,w;}edge[maxn],edgec[maxn] ;
int n,tot,m,head[maxn],low[maxn],dfn[maxn],headc[maxn],
tc,cnt,num ,stck[maxn],ins[maxn],top,c[maxn],deg[maxn] ;
vector<int> scc[maxn] ;
ll res[maxn] ;
void add(int u,int v,int w) {
edge[++tot].ver=v; edge[tot].next=head[u];
edge[tot].w=w; head[u]=tot; return ;
}
void addc(int u,int v,int w) {
edgec[++tc].ver=v; edgec[tc].next=headc[u];
edgec[tc].w=w; headc[u]=tc; return ;
}
void tarjan(int x) {
low[x]=dfn[x]=++num;
stck[++top]=x; ins[x]=1;
for(int i=head[x],y;i;i=edge[i].next) {
if(!dfn[y=edge[i].ver]) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]) {
cnt++; int z;
do{
z=stck[top--]; ins[z]=0;
c[z]=cnt; scc[cnt].push_back(z);
} while(z!=x);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>n>>m;
while(m--) {
int a,b,t; cin>>t>>a>>b;
if(t==1) add(a,b,0),add(b,a,0);
else if(t==2) add(a,b,1);
else if(t==3) add(b,a,0);
else if(t==4) add(b,a,1);
else add(a,b,0);
} //强连通分量
for(int i=1;i<=n;i++) {
if(!dfn[i]) tarjan(i);
} //缩点
for(int x=1;x<=n;x++) { //遍历所有的边
for(int i=head[x],y;i;i=edge[i].next) {
if(c[x]!=c[y=edge[i].ver]) {
addc(c[x],c[y],edge[i].w);
deg[c[y]]++; //入度数
} else if(edge[i].w!=0) { //判无解
cout<<-1<<endl;
return 0;
}
}
} //处理DAG图-topo法
queue<int> q;
fill(res+1,res+1+n,1); //初始化
for(int i=1;i<=cnt ;i++) {
if(deg[i]==0) q.push(i);
} ll ans=0;
while(q.size() ) {
int x=q.front(); q.pop();
ans+=res[x]*scc[x].size() ; //本连通块中的亮度总和
for(int i=headc[x],y;i;i=edgec[i].next) {
y=edgec[i].ver;
res[y]=max(res[y],res[x]+edgec[i].w); //连通块亮度
deg[y]--;
if(deg[y]==0) q.push(y);
}
} cout<<ans<<endl;
return 0;
}