莫欺少年穷,修魔之旅在这开始—>算法提高课题解
思路:
1. 求最小值即求最长路(正环)
2. 建边
3. tarjan 缩点
4. 建立新图,如果两个点在同一个连通块并且存在正边,则存在正环,不符合条件
5. 按拓扑序列求最长路
可参考: 糖果
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010, M = 600010;
int n,m;
int h[N],hs[N],e[M],w[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,sz[N];
int dist[N];
void add(int h[],int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++timestamp;
stk[++top]=u,in_stk[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
}
if(dfn[u]==low[u])
{
scc_cnt++;
int y;
do {
y=stk[top--];
in_stk[y]=false;
id[y]=scc_cnt;
sz[scc_cnt]++;
} while(y!=u);
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) add(h,0,i,1);
//建边
while(m--)
{
int t,a,b;
cin>>t>>a>>b;
if(t==1) add(h,b,a,0),add(h,a,b,0);
else if(t==2) add(h,a,b,1);
else if(t==3) add(h,b,a,0);
else if(t==4) add(h,b,a,1);
else add(h,a,b,0);
}
//缩点
tarjan(0);
memset(hs,-1,sizeof hs);
//建立新图
bool flag=true;
for(int i=0;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])
{
int k=e[j];
int a=id[i],b=id[k];
if(a==b&&w[j])
{
//在同一个连通块中且存在正环,不符合条件
flag=false;
break;
}
if(a!=b) add(hs,a,b,w[j]);
}
if(!flag) break;
}
//按拓扑序列求最长路
if(!flag) cout<<-1<<endl;
else
{
for(int i=scc_cnt;i;i--)
for(int j=hs[i];~j;j=ne[j])
{
int k=e[j];
dist[k]=max(dist[k],dist[i]+w[j]);
}
LL res=0;
for(int i=1;i<=scc_cnt;i++) res+=(LL)dist[i]*sz[i];
cout<<res<<endl;
}
return 0;
}