解题报告+板子：luogu P3387 【模板】缩点

题目链接：P3387 【模板】缩点

缩点板子，所谓\(dp\)就是拓扑排序（毕竟可以重走边），像\(SPFA\)一样松弛就好，就是重边极其烦人，还加了排序（绝对自己想的，然鹅拓扑的思路不是）。

下面上代码：

（为了突出惨烈性，我把调试语句留了下来......）

\(Code\):

#include<iostream>

#include<cstdio>

#include<cstring>

#include<stack>

#include<queue>

#include<algorithm>

using namespace std;

const int MAXN=1e5+5;

struct node

{

	int to,nxt;

}e[MAXN],g[MAXN];

int heade[MAXN],cnte=0;

int headg[MAXN],cntg=0;

void adde(int u,int v)

{

	e[++cnte].to=v;

	e[cnte].nxt=heade[u];

	heade[u]=cnte;

}

void addg(int ux,int vx)

{

	g[++cntg].to=vx;

	g[cntg].nxt=headg[ux];

	headg[ux]=cntg;

}

int low[MAXN],num[MAXN],belong[MAXN],vis[MAXN];

int c=0,val[MAXN];

stack<int> s;

queue<int> q;

int indexx=0;

int n,m,l,r,w[MAXN];

void dfs1(int cur,int fa)

{

	low[cur]=++indexx;

	num[cur]=indexx;

	s.push(cur);

	vis[cur]=1;

	for(int i=heade[cur];i;i=e[i].nxt)

	{

		int j=e[i].to;

		if(!low[j]) dfs1(j,cur),low[cur]=min(low[cur],low[j]);

		else if(vis[j])low[cur]=min(low[cur],num[j]);

	}

	if(low[cur]==num[cur])

	{

		int k;

		c+=1;

		do

		{

			k=s.top();

			s.pop();

			vis[k]=0;

			belong[k]=c;

			val[c]+=w[k];

		}while(cur!=k);

	}

}

int b[MAXN],maxn=0,deg[MAXN],dis[MAXN]={0};

struct gg

{

	int uu,vv;

}dl[MAXN];

int cuv=0;

bool cmp(gg n,gg m)

{

	if(n.uu^m.uu) return n.uu<m.uu;

	else return n.vv<m.vv;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) scanf("%d",&w[i]);

	for(int i=1;i<=m;i++) scanf("%d%d",&l,&r),adde(l,r);

	for(int i=1;i<=n;i++) if(!low[i]) dfs1(i,i);

	/*for(int i=1;i<=n;i++) cout<<belong[i]<<" ";

	cout<<endl;

	for(int i=1;i<=c;i++) cout<<val[i]<<" ";

	cout<<endl;*/

	for(int i=1;i<=n;i++)

	{

		for(int x=heade[i];x;x=e[x].nxt)

		{

			int j=e[x].to;

			int k=belong[i];

			int t=belong[j];

			if(t^k) dl[++cuv].uu=k,dl[cuv].vv=t;

			//addg(k,t),deg[t]++,cout<<k<<" "<<t<<"\n";

		}

	}

	//cout<<endl;

	sort(dl+1,dl+cuv+1,cmp);

	int lu=-1,lv=-1;

	for(int i=1;i<=cuv;i++)

	{

		if((dl[i].uu!=lu)||(dl[i].vv!=lv))

		{

			//cout<<dl[i].uu<<" "<<dl[i].vv<<"\n";

			addg(dl[i].uu,dl[i].vv);

			lu=dl[i].uu,lv=dl[i].vv;

			deg[dl[i].vv]++;

		}

		else continue;

	}

	/*for(int i=1;i<=c;i++) cout<<deg[i]<<" ";

	cout<<endl;

	for(int i=1;i<=c;i++)

	{

		for(int j=headg[i];j;j=g[j].nxt) cout<<g[j].to<<" ";

		cout<<"\n";

	}*/

	for(int i=1;i<=c;i++)

	{

		if(!deg[i]) q.push(i);

	}

	for(int i=1;i<=c;i++) dis[i]=val[i];

	while(!q.empty())

	{

		int now=q.front();

		q.pop();

		//cout<<now<<" ";

		for(int i=headg[now];i;i=g[i].nxt)

		{

			int j=g[i].to;

			deg[j]--;

			dis[j]=max(dis[j],dis[now]+val[j]);

			if(!deg[j]) q.push(j);

		}

	}

	//cout<<endl;

	for(int i=1;i<=c;i++) maxn=max(maxn,dis[i]);

	//for(int i=1;i<=c;i++)cout<<dis[i]<<" ";

	printf("%d\n",maxn);

	return 0;

}

其实除了码量还挺朴素的......

巴特西

解题报告+板子：luogu P3387 【模板】缩点

\(Code\):

最新文章

热门文章