申請SAE

如果您發現本博客的外觀很難看,那是因為部分外觀文件被中國.國家.防火.牆屏.蔽所致!
請翻~牆!

我的Wordpress博客的地址: http://zhuyf.tk/

2012年2月27日 星期一

圖論練習題 圖的平方 ljb

【問題描述】
有向圖G=(V,E)的平方是圖G^2=(V,E^2),該圖滿足下列條件:(u,w)∈E^2當且僅當對v∈V,有(u, v)∈E,且(v,w)∈E。亦即,如果圖G中頂點u和w之間存在著一條恰包含兩條邊的路徑時,則G^2必包含該邊(u,w)。
請編程序對於給定的有向圖G,查詢邊(u,w)是否存在於平方圖G^2中。
【輸入文件】
第一行有兩個整數,v(1<=v<=100000),m(1<=m<=1000),其中v表示圖G的頂點個數,(頂點按1~v編號);
接下來有m行,每行包含4個整數u1,u2,v1,v2,表示在圖G中,頂點區間[u1,u2]中的每一個頂點至頂點區間[v1,v2]中的每一個頂點都有邊相連;
接下來有一行,一個整數n(1<=n<=1000),表示查詢的個數;
接下來有n行,每一行有4個整數,x1,x2,y1,y2,表示一個詢問,即詢問在平方圖G^2中,其頂點區間[x1,x2]中的每一個頂點至頂點區間[y1,y2]中的每一個頂點是否都有邊。

 
【輸出文件】
對於每一個查詢,如果結果為“是”則輸出"Yes",否則輸出"No",如果有多個查詢,每個結果單獨佔一行。
【樣例輸入】
ljb.in
6 2
1 3 5 6
4 5 2 3
1
2 3 4 6
【樣例輸出】
ljb.out
No
注:圖G與G^2中的邊數均不會超過2000000.

【我的代碼】

C++语言: Codee#25683
01 #include <cstdio>
02 #include <cstdlib>
03 #include <vector>
04 #include <algorithm>
05 #include <cstring>
06 using namespace std;
07 const int MAXN=100001;
08 typedef vector<int> Vec;
09 Vec Map[MAXN];
10
11 int N,M;
12 void init()
13 {
14     scanf("%d %d\n",&N,&M);
15     int a,b,c,d;
16     for(int i=1;i<=M;i++)
17     {
18         scanf("%d %d %d %d\n",&a,&b,&c,&d);
19         for(int j=a;j<=b;j++)
20         {
21             for(int k=c;k<=d;k++)
22             {
23                 Map[j].push_back(k);
24             }
25         }
26     }
27 }
28
29 void solve()
30 {
31     int V;
32     scanf("%d\n",&V);
33     int a,b,c,d;
34     int flg[MAXN];
35     for(int i=1;i<=V;i++)
36     {
37         scanf("%d %d %d %d\n",&a,&b,&c,&d);
38         bool flag=true;
39         int num;
40         int nxt;
41         for(int j=a;j<=b;j++)
42         {
43             num=d-c+1;
44             memset(flg,0,sizeof(flg));
45             for(unsigned int k=0;num>0&&k<Map[j].size();k++)
46             {
47                 nxt=Map[j][k];
48                 for(unsigned int l=0;num>0&&l<Map[nxt].size();l++)
49                 {
50                     if(Map[nxt][l]>=c && Map[nxt][l]<=d)
51                     {
52                         if(!flg[Map[nxt][l]])
53                         {
54                             num--;
55                             flg[Map[nxt][l]]=1;
56                         }
57                     }
58                 }
59             }
60             if(num!=0)
61             {
62                 flag=0;
63                 break;
64             }
65         }
66         if(flag)
67             printf("Yes\n");
68         if(!flag)
69             printf("No\n");
70     }
71 }
72
73 int main()
74 {
75     freopen("ljb.in","r",stdin);
76     freopen("ljb.out","w",stdout);
77     init();
78     solve();
79     return 0;
80 }

沒有留言:

張貼留言