傳送門

這道題還是比較容易看出是tarjan的。首先我們知道如果學校之間成環(huán)的話那么學校之間一定能到達，直接縮成一個點就好了。

縮完點之后我們得到了一個DAG。之后因為子任務A要求的是最少接受新軟件的學校有多少個，可以很容易的想出我們只要給所有入度為0的學校發(fā)一份就可以了，因為剩下的必然是可以從其他學校傳過來的嘛。

子任務A的答案就是DAG中入度為0的點數。

至于子任務2，我們要求的就是把這個圖變?yōu)閺娺B通分量至少要加幾條邊。思考之后發(fā)現，一個點如果入度為0，那么它就無法被其他學校傳進來，那么就不行，然后如果一個點出度為0，他就無法傳出，也不行。所以我們直接統(tǒng)計一下入度為0和出度為0的點數，兩者最大值則為結果。（因為我們至少要保證所有點都有至少一個入度和出度，最優(yōu)策略就是把入度為0和出度為0的點連邊，剩下的隨便連即可，所以是最大值）

然后如果整個圖全都在一個強連通分量中，需要進行特判（會認為當前的DAG沒有出度）

看一下代碼。

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #include<map> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar('\n')using namespace std; typedef long long ll; const int M = 50005;int read() {int ans = 0,op = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') op = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * op; }struct edge {int next,to,from; }e[M<<2],e1[M<<2]; int n,m,cnt,ecnt,cur,low[M],dfn[M],stack[M],top,curr,vis[M],belong[M],head[M],ecnt1,head1[M]; int rdeg[M],cdeg[M],sum1,sum2,tot; bool in[M],pd[M];void add(int x,int y) {e[++ecnt].to = y;e[ecnt].next = head[x];e[ecnt].from = x;head[x] = ecnt; }void tarjan(int x) {dfn[x] = low[x] = ++cnt;in[x] = 1,stack[++top] = x;for(int i = head[x];i;i = e[i].next){if(!dfn[e[i].to]) tarjan(e[i].to),low[x] = min(low[x],low[e[i].to]);else if(in[e[i].to]) low[x] = min(low[x],dfn[e[i].to]);}if(low[x] == dfn[x]){int p;while(p = stack[top--]){belong[p] = x,in[p] = 0;pd[x] = 1;if(p == x) break;}} } void rebuild() {rep(i,1,ecnt){int r1 = belong[e[i].to],r2 = belong[e[i].from];if(r1 != r2){e1[++ecnt1].to = r1;e1[ecnt1].from = r2;e1[ecnt1].next = head1[r2];head1[r2] = ecnt1;rdeg[r1]++,cdeg[r2]++;}} }int main() {n = read();rep(i,1,n){while(1){m = read();if(!m) break;add(i,m);}}rep(i,1,n) if(!dfn[i]) tarjan(i);rebuild();rep(i,1,n){if(!pd[i]){curr++;continue;}if(!rdeg[i]) sum1++;if(!cdeg[i]) sum2++;}printf("%d\n",sum1);if(curr == n-1) printf("0\n");else printf("%d\n",max(sum1,sum2));return 0; }

?

轉載于:https://www.cnblogs.com/captain1/p/9680827.html

總結

以上是生活随笔為你收集整理的[USACO5.3]校园网Network of Schools的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。