Description

題目背景
。飛紛火戰(zhàn)來年近國 D 和國 C
。飛亂子鴿來年近國 D 和國 C
題面描述
最近，C 國成功地滲透進入了 D 國的一個城市。這個城市可以抽象成一張有 n 個節(jié)點，節(jié)點之間有 m 條雙向道路連接的無向圖，每條道路的?度都為 1 。
經(jīng)過偵查，C 國情報部部? GGB 驚訝地發(fā)現(xiàn)，這座看起來不起眼的城市竟然是 D 國的軍事中心。因此 GGB 決定在這個城市內(nèi)設(shè)立情報機構(gòu)。情報專家 TAC 在偵查后，安排了 q 種設(shè)立情報機構(gòu)的方案。這些方案中，第 i 種方案將計劃建立 ki 個情報機構(gòu)，第 j 個情報機構(gòu)可以安排人員到距離其不超過 di,j 的節(jié)點上收集情報。

Input

從文件 center.in 中讀入數(shù)據(jù)。
輸入第一行包含三個正整數(shù) n, m, q ，分別表示城市的節(jié)點個數(shù)、道路條數(shù)和方案個數(shù)。
接下去 m 行每行兩個正整數(shù) u, v ，表示存在一條連接城市 u 和城市 v 的雙向道路。
接下去 q 行，每行表示一個方案。第一個正整數(shù) k 表示該種方案將計劃建立 k 個情報機構(gòu)，之后是 2k 個正整數(shù)，其中第 2i ? 1 個數(shù)表示方案中第 i 個情報機構(gòu)所在的節(jié)點編號，第 2i 個數(shù)表示第 i 個情報點所能派出情報人員的最遠距離。

Output

輸出到文件 center.out 中。
輸出包含 q 行，每行包含一個整數(shù)，表示相應(yīng)詢問的答案。

Sample Input

5 8 3
1 2
1 3
1 4
1 5
2 4
2 5
3 5
4 5
1 2 1
1 1 1
2 2 2 3 1

樣例 2
見選手目錄下的 center/center2.in 與 center/center2.ans 。

Sample Output

4
5
5

Data Constraint

題目更正：di,j值域在int范圍內(nèi)；q小于等于100000

Solution

• 這題暴力的話是 $O(n\sum k)$ ，就是預(yù)處理出兩點距離，然后枚舉點看其能否被到達。

• 但是這樣顯然不能通過此題。

• 考慮使用STL的 $bitset$ 來優(yōu)化并解決此題。

• 設(shè) $bitset<N>f[i][j]$ ，表示從點 $i$ 出發(fā)，走不超過 $j$ 的距離能到達的點的集合。

• 這樣設(shè)的空間復(fù)雜度是 $O(\frac{n^3}{32})$ 的，不會爆空間（卡得還真緊……）。

• 于是我們預(yù)處理 $f$ ，比如到一個點 $i$ 走距離 $d$ 恰好走到 $x$ ，則 $f[i][d][x]=1$ 。

• 最后對 $f[i]$ 做一遍前綴或運算即可，即：$f[i][j]|=f[i][j?1]$

• 那么回答詢問就容易啦！將每個 $f[x][d]$ 或起來，輸出 $bitset$ 集合中 $1$ 的個數(shù)就好了。

• 然而這題還要卡常，如果用前向星等鏈表、vector存儲邊的話還會 $TLE$ 。

• 為了尋址復(fù)雜度更優(yōu)，我們可以用鄰接表來存邊。。

• 注意還要用一個鄰接矩陣來判斷重邊，不然還會爆鄰接表數(shù)組。。（自環(huán)當(dāng)然也要判）

• 時空復(fù)雜度 $O(\frac{n^3}{32})$ 。

Code

#include<cstdio> #include<cstring> #include<bitset> #include<cctype> using namespace std; const int N=1005; int a[N][N],dis[N],que[N],mx[N]; bool bz[N][N]; bitset<N>f[N][N],ans; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int min(int x,int y) {return x<y?x:y; } int main() {freopen("center.in","r",stdin);freopen("center.out","w",stdout);int n=read(),m=read(),q=read();for(int i=1;i<=m;i++){int x=read(),y=read();if(x==y || bz[x][y]) continue;a[x][++a[x][0]]=y;a[y][++a[y][0]]=x;bz[x][y]=bz[y][x]=true;}for(int i=1;i<=n;i++){memset(dis,60,sizeof(dis));dis[que[1]=i]=0;f[i][0][i]=1;int l=0,r=1;while(l<r){int x=que[++l];for(int j=1;j<=a[x][0];j++){int y=a[x][j];if(dis[x]+1<dis[y]){f[i][dis[y]=dis[x]+1][y]=1;que[++r]=y;}}}int up=mx[i]=dis[que[r]];for(int j=1;j<=up;j++) f[i][j]|=f[i][j-1];}while(q--){ans.reset();int k=read();while(k--){int x=read(),d=min(mx[x],read());ans|=f[x][d];}write(ans.count()),putchar('\n');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5932. 【NOIP2018模拟10.27】情报中心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。