首先转换图论模型, 把某个客户一个终端的维修时间 (+1)%h 之后和另一个终端维修时间一样, 这样的两个终端连一条有向边, 表示推后一个终端就必须推后另一个
然后 tarjan 缩点, 一个 scc 里的终端是要一起推迟的, scc 内点数为新图点权
根据贪心的思想, 在缩完点的 DAG 里, 一定是出度为 0 的点能获得更小的值, 因为出度不为零的点还要加上出边所能到的点的点权
直接在出度为 0 的点里取 min, 然后记一下更新答案的新点, 最后把属于这个新点的点的编号输出即可
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int N=1000005;
- int n,m,q,a[N],h[N],cnt,low[N],dfn[N],tot,bl[N],col,s[N],top,d[N],va[N],mn=1e9,w;
- bool v[N];
- struct qwe
- {
- int ne,no,to;
- }e[N];
- int read()
- {
- int r=0,f=1;
- char p=getchar();
- while(p>'9'||p<'0')
- {
- if(p=='-')
- f=-1;
- p=getchar();
- }
- while(p>='0'&&p<='9')
- {
- r=r*10+p-48;
- p=getchar();
- }
- return r*f;
- }
- void add(int u,int v)
- {
- cnt++;
- e[cnt].ne=h[u];
- e[cnt].no=u;
- e[cnt].to=v;
- h[u]=cnt;
- }
- void tarjan(int u)
- {
- dfn[u]=low[u]=++tot;
- v[s[++top]=u]=1;
- for(int i=h[u];i;i=e[i].ne)
- {
- if(!dfn[e[i].to])
- {
- tarjan(e[i].to);
- low[u]=min(low[u],low[e[i].to]);
- }
- else if(v[e[i].to])
- low[u]=min(low[u],dfn[e[i].to]);
- }
- if(low[u]==dfn[u])
- {
- col++;
- while(s[top]!=u)
- {
- bl[s[top]]=col;
- va[col]++;
- v[s[top--]]=0;
- }
- bl[s[top]]=col;
- va[col]++;
- v[s[top--]]=0;
- }
- }
- int main()
- {
- n=read(),m=read(),q=read();
- for(int i=1;i<=n;i++)
- a[i]=read();
- for(int i=1;i<=m;i++)
- {
- int x=read(),y=read();
- if((a[x]+1)%q==a[y])
- add(x,y);
- if((a[y]+1)%q==a[x])
- add(y,x);
- }
- for(int i=1;i<=n;i++)
- if(!dfn[i])
- tarjan(i);
- for(int i=1;i<=cnt;i++)
- if(bl[e[i].no]!=bl[e[i].to])
- d[bl[e[i].no]]++;
- for(int i=1;i<=col;i++)
- if(!d[i]&&va[i]<mn)
- mn=va[i],w=i;
- printf("%d\n",mn);
- for(int i=1;i<=n;i++)
- if(bl[i]==w)
- printf("%d",i);
- return 0;
- }
- codeforces 949C - Data Center Maintenance[tarjan]
来源: http://www.bubuko.com/infodetail-2676285.html