Contest 1094

第一題：1543 -- 分組

看不到沒關系：

Description

資訊學競賽班的班主任 \text{Smart}Smart 是一位心思很缜密的老師，他在接手資訊學競賽班一個學期以後，想調查一下班上同學之間互相交流的情況，以便及時了解班級動态。

資訊學競賽班一共有 nn 個同學。這 nn 位同學每一個人都有一個小花名冊，名冊裡面寫着他所願意交流的人的名字。比如說在 AA 的人名單裡寫了 BB，那麼表示 AA 願意與 BB 交流；但是 BB 的名單裡不見得有 AA，也就是說 BB 不見得想與 AA 交流。但是如果 AA 願意與 BB 交流，BB 願意與 CC 交流，那麼 AA 一定願意與 CC 交流。也就是說交流有傳遞性。

班主任 \text{Smart}Smart 覺得需要将這 nn 個人分為 mm 組，要求每一組的任何一人都願意與組内其他人交流。并求出一種方案以确定 mm 的最小值是多少。

Input

第一行一個整數 nn（1≤n≤2001≤n≤200）。

接下來 nn 行，第 (i+1)(i+1) 行表示編号為 ii 的人的小花名冊名單，名單以 00 結束。

注意：自己的名單裡面不會有自己的名字。

Output

一行，一個整數 mm 。

Sample Input

2 0

1 0

4 5 0

3 0

4 0

Sample Output

Sample Explanation

樣例中 11 和 22 分在一組，33、44 和 55 分在一組。

Hint

100\%100%的資料：1≤n≤2001≤n≤200。

Source

程式設計提高班

一.題目大意

今天的比賽是FLOYD專題，是以先用兩句話概括一下FLOYd

好那麼首先floyd是o(n^3)的算法，也就是說今天三道題（後兩道沒搞懂。。。）的資料範圍都在300以内

然後FLOYD算法本身就是三層循環：k階段，i,j狀态，是以k放在第一層循環，而i,j的順序不重要

方程會分成兩種不同的用途

1.求最短路徑（第三題）：f[i][j]=max(f[i][k]+f[k][j],f[i][j])

2.求閉包（好家夥，閉包是個啥），額麼麼，閉包就是說a->b，b->c 那麼一定有a->c也可以先粗略的認為就是強聯通分量之後再變化一下

那麼第一道題，其實就是強聯通分量

二.算法思路

就是讓你把盡量多的同學分成一組，然後求有多少組，求強聯通分量少不了FLOYD算法（當然塔楊算法更好）

現在，我們使用FLOYD求出了任意兩點是否連通，然後呢

我們就按照算出來的數組進行模拟，把那些可以互達的點合并到一組，統計最終的組數就行了

三.代碼實作

#include<bits/stdc++.h>
using namespace std;

const int N=205;

int f[N][N];
int a[N][N],cnt[N],n;

int read(){
	int a=0;char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))a=a*10+c-'0',c=getchar();
	return a; 
}

int ans;

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		int tmp=read();
		while(tmp){
			f[i][tmp]=1;
			tmp=read();
		}
		f[i][i]=1;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=f[i][j] || (f[i][k] && f[k][j]);
			}
		}
	} 
	int vis[N]={0};
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		ans++;
		for(int j=1;j<=n;j++){
			if(f[i][j])vis[j]=1;
		}
	}
	printf("%d\n",ans); 
	return 0;
}

第二題：1562 -- 舞會邀請

看不到沒關系：

1562 -- 舞會邀請

Description

\text{Smart}Smart 是一位頗有成就的藝術家，他因油畫作品《我愛北京天安門》聞名于世界。現在，他為了報答幫助他的同行們，準備開一個舞會。

\text{Smart}Smart 準備邀請 nn 個已經确定的人，可是問題來了：

這 nn 個人每一個人都有一個小花名冊，名冊裡面寫着他能夠通知到的人的名字。比如說在 AA 的人名單裡寫了 BB，那麼表示 AA 能夠通知到 BB；但是 BB 的名單裡不見得有 AA，也就是說 BB 不見得能夠通知到AA。

\text{Smart}Smart 覺得需要确定自己需要通知到多少個人（人數mm），能夠實際将所有 nn 個人都通知到。并求出一種方案以确定 mm 的最小值是多少。

注意：自己的名單裡面不會有自己的名字。

Input

第一行一個數 nn。

接下來 nn 行，第 i+1i+1 行表示編号為 ii 的人的小花名冊名單，名單以 00 結束。

Output

一個整數，即 mm 的值。

Sample Input

5 2 0

5 3 0

5 4 0

5 1 0

2 0

Sample Output

Hint

100\%100%的資料：1≤n≤2001≤n≤200。

Source

程式設計提高班

一.題目大意

這道題比上道題就少一個限制（如果代碼原封不動送出能夠那50PTS）：隻需要單向告知，不需要互達

二.算法思路

如果還是用FLOYD算法計算強聯通分量，也可以，然後我們可以認為，一個強連通分量在圖中的地位就是一個宏觀意義上的點

那麼就可以縮點（親測可以過，但是要76行代碼）

然後就想一想可不不可以偷個懶（主要是縮點我不會2333）

那實際上我們可以使用一種巧妙地算法：就是設f[i]表示通知f[i]的人，那麼如果i、j連通，我就可以讓i通知J

那麼就是f[j]=f[i]，而初始化就是f[i]=i，也就表示是自己通知自己，也就是憑空想出來（必須），那麼所有必須瞎猜的人就是我必須要通知的人

三.代碼實作

#include<bits/stdc++.h>
using namespace std;

const int N=205;

int f[N],a[N][N],n,x,y;

inline int read(){
	int a=0;char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))a=a*10+c-'0',c=getchar();
	return a;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		int tmp=read();
		while(tmp!=0){
			a[i][tmp]=1;
			tmp=read();
		}
		f[i]=i;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j || j==k || i==k)continue;
				a[i][j]|=a[i][k] && a[k][j];
			}
		}
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]==1){
				//可以互達
				f[j]=f[i];//就讓 i 告訴 j  
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans+=(f[i]==i);
	printf("%d\n",ans);
	return 0;
}

四.細節聚焦

就是這種思路特别想并查集

那麼我們可不可以往并查集上湊一下，把他改成并查集的思路

實際上就是并查集！

我們所有能夠收到一個人通知（我們稱消息大發源地為通知者）的人，都是一個集合，而隊長就是那個無法得到通知而編造“謠言”的人

然後我去告訴這些造謠的人，說你們是對的，然後就是最少的通知人數

是以第一題是求有向圖連通+強連通分量模拟

第二題是求有向圖連通+并查集求集合數

第三題：1546 -- 最短路上的統計

看不見沒關系：

1546 -- 最短路上的統計

Description

一個無向圖上，沒有自環，所有邊的權值均為 11，對于一個點對 (a,ba,b)，我們要把所有 aa 與 bb 之間所有最短路上的點的總個數輸出。

Input

第一行兩個整數 n,mn,m，表示 nn 個點，mm 條邊；

接下來 mm 行，每行兩個數 a,ba,b，表示 a,ba,b 之間有條邊；

接下來一個整數 pp，表示問題的個數；

接下來 pp 行，每行兩個數 a,ba,b，表示詢問 a,ba,b。

Output

對于每個詢問，輸出一行包含一個數cc，表示 a,ba,b 之間最短路上點的總個數。

Sample Input

5 6

1 2

1 3

2 3

2 4

3 5

4 5

2 5

5 1

2 4

Sample Output

Hint

100\%100% 的資料：N≤100,p≤5000N≤100,p≤5000。

Source

程式設計提高班

一.題目大意

這個題就是讓你求任意兩點之間最短路徑的所有情況畫出來之後會覆寫多少個點

二.算法思路

那麼首先求最短路徑，而且是多元的，那就是FLOYD一定的

求完之後，我們思考某一個點為什麼有資格被統計？

就是他一定是最短路徑中某一種的某一個轉折點！

轉換成計算機語言就是f[i][k]+f[k][j]==f[i][j]的所有k點

然後就是把FLOYD算一遍然後讀入a,b并且周遊1~n并且同時尋找所有的k統計下來

三.代碼實作

#include<bits/stdc++.h>
using namespace std;

const int N=105;

int n,m,a,b,d[N][N],p,ans;

inline int read(){
	int a=0;char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))a=a*10+c-'0',c=getchar();
	return a;
}

int main(){
	n=read(),m=read();
	memset(d,0x3f,sizeof d);
	for(int i=1;i<=m;i++){
		a=read(),b=read();
		d[a][b]=1;
		d[b][a]=1;
	} 
	for(int i=1;i<=n;i++)d[i][i]=0;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	p=read();
	for(int i=1;i<=p;i++){
		a=read(),b=read(); 
		for(int k=1;k<=n;k++){
			if(d[a][k]+d[k][b]==d[a][b])ans++;
		}
		printf("%d\n",ans);
		ans=0;
	}
	return 0;
}

四.宏觀思路

那麼這道題為什麼能想到這個

首先這道題實際上是變相的要求你計算出最短路徑的具體參數而非單單的長度，你隻有知道了這些才能回答問題

那麼多元最短路徑在不止一條的時候怎麼全部“輸出” ？

這就好逼問你，最長不下降子序列/最長公共子序列到第長啥樣一個道理

DP倒推得到路徑

這是一個很重要的知識點

知識這個地方不止一條路徑，是以沒法追根溯源（計算機同時隻能執行一個，無法真正達到層次周遊）

那麼就尋找所有的中間狀态

那麼這個地方就需要證明一個東西

那就是為什麼有且隻有f[i][k]+f[k][j]==f[i][j]的時候k是i到j的墊腳石，

問題一：對于為什麼沒有其他方面是的問題

證明：如果有不是這樣條件是的話，那麼最短路徑就會變短，那麼反之最短路徑又變成了f[i][k']+f[k'][j]==f[i][j]但如果這樣的話在原先的FLOYD算法中就已經應該更新過了

問題二：對于為什麼滿足則一定是的問題

證明：由于是進行了n輪求最短路松弛的操作猜得到了狀态數組，那麼最後一次的任何一個f[i][k]或者f[k][j]都一定參與過f[i][j]的計算，也就是說如果最後一次的F[i][k]+f[k][j]==f[i][j]，那麼f[i][k]+f[k][j]一定松弛過f[i][j]，那麼就一定是最短路徑！

無論對于墊腳石k1還是k2還是路人甲，隻要自己作為斷點的時候影響到了最優解，就一定是這個嘴有點的一個狀态（決策）

題解報告：contest 1094一.題目大意二.算法思路三.代碼實作一.題目大意二.算法思路三.代碼實作四.細節聚焦一.題目大意二.算法思路三.代碼實作四.宏觀思路

Description

Input

Output

Sample Input

Sample Output

Sample Explanation

Hint

Source

一.題目大意

二.算法思路

三.代碼實作

1562 -- 舞會邀請

Description

Input

Output

Sample Input

Sample Output

Hint

Source

一.題目大意

二.算法思路

三.代碼實作

四.細節聚焦

1546 -- 最短路上的統計

Description

Input

Output

Sample Input

Sample Output

Hint

Source

一.題目大意

二.算法思路

三.代碼實作

四.宏觀思路

繼續閱讀