題目3 : 八卦的小冰

時間限制:2000ms 單點時限:1000ms 內存限制:256MB

描述

小冰是個八卦的人，最近她對一個社交網站很感興趣。

由于小冰是個機器人，所以當然可以很快地弄清楚這個社交網站中用戶的信息啦。

她發現這個社交網站中有N個用戶，用戶和用戶之間可以進行互動。小冰根據用戶之間互動的次數和內容判斷每對用戶之間的親密度。親密度非負，若大于零表示這兩個用戶之間是好友關系。由于這個網站是活躍的，所以小冰會不停地更新用戶之間的親密度。

由于隱私保護，小冰無法知道每個用戶的確切性別，但是作為一只很聰明的人工智能，小冰可以通過每個用戶的行為來猜測性別。當然這種猜測是不準確的，小冰有可能會改變對一個用戶的判斷。

小冰想知道這個社交網絡的八卦度是多少。八卦度的定義是社交網絡中所有異性好友之間的親密度之和。你能幫助她嗎？

輸入

第一行一個整數T，表示數據組數。接下來是T組數據，每組數據的格式如下：

第一行是三個整數N, M, Q，分別表示用戶數、初始的好友對數、操作數。

第二行是N個空格隔開的數，第i個數表示i號用戶的性別，用0或1表示。

接下來的M行，每行三個數x, y, z，代表初始狀態用戶x和用戶y之間的親密度是z。除此之外的用戶之間的親密度初始為0。

接下來是Q行，每行是以下三種操作中的一種：

1. “1 x”：改變用戶x的性別

2. “2 x y z”：改變用戶x與用戶y之間的親密度為z

3. “3”：詢問八卦度

輸出

對于每組數據首先輸出一行"Case #X:"，X為測試數據編號。

接下來對于每一個詢問，輸出一行包含詢問的八卦度。

數據范圍

1 ≤ T ≤ 20

1 ≤ x, y ≤ N

0 ≤ z ≤ 100000

小數據

1 ≤ N, M ≤ 100

1 ≤ Q ≤ 1000

大數據

1 ≤ N, M, Q ≤ 100000

樣例輸入

1 3 2 8 0 1 0 1 2 1 1 3 1 3 1 1 1 2 3 2 2 3 2 3 1 2 3

樣例輸出

Case #1: 1 2 2 3

EmacsNormalVim 題意：構建無向圖，成員編號是1~N，每個成員當作一個點，而且每個成員有分男女性別，在這無向圖中，每一條邊表示兩個成員之間的親密度，詢問異性之間親密度的總和。一開始讓如每一個成員的性別用 0 1表示，在輸入初始化的無向圖。輸入操作數1 x，表示改變x編號成員的性別，輸入操作數2 x?y z，表示改變編號x和編號y的親密度為z，輸入操作數3 ，詢問異性之間親密度的總和，在于題目的大數據點和邊都比較大，用臨街矩陣做不了，需要采用的是用鄰接表來實現記錄無向圖。 題目的難點在于對于每一次的詢問，如果都要進行查找，則會超時。 1,所以，用sum來記錄異性親密度總和，在初始的無向圖時，判斷下性別，累加異性的親密度。 2,在修改性別也同樣更新sum，因為改變性別的，結果只是會影響到與該點所連接的親密度是否需要累加， a，如果修改后性別一樣，說明之前性別不一樣，也就是之前就有加過這個頂點的權值了，而且，現在性別一樣，所以sum需要減去這頂點的的權值來實現更新； b，如果修改后性別不一樣，說明之前的性別一樣，也就是之前沒有加上該頂點的權值，現在性別不一樣，所以，sum直接加上當前頂點的權值來實現更新； 3,如果修改的是兩個成員的關系，則有可能是添加新的邊或者是修改已經有的點的權值。如果是修改已有邊的權值需要你去查找改變，并且更新sum，如果是新建邊，則只需要繼續累加sum即可； 4，題目中的邊數量可能會比較大，在操作的時候，可能一直添加邊，提交結果有時候確實TLE而不是RE，囧囧囧。。。 PS：鏈表的邊數=無向圖邊數*2，這個忘記了導致出錯，判斷居然還是提示TLE而不是RE,囧囧囧囧。。。 一下代碼使用兩種方法記錄答案，一個是按照邊數記錄，一個是按照鏈表的邊數記錄； 1 /*記錄無向圖的邊數*/ 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #define MAX 100010 6 using namespace std; 7 int SEX[100010]; //性別 8 typedef struct edge 9 { 10 int TO; //下一個頂點 11 int Next; //記錄下一條邊的編號 12 int Vlaue; //權值 13 }EDGE; 14 EDGE ID[3*MAX]; //邊表,坑爹的邊數，記得弄多點，不然有時候也會提示超時。 15 int First[MAX]; //First[x]：x表示頭結點為x，First[x]表示下一條邊的編號 16 int SIGN; 17 long long sum; 18 void Add_E(int x,int y,int z) //添加邊 19 { 20 ID[SIGN].TO=y; 21 ID[SIGN].Vlaue=z; 22 ID[SIGN].Next=First[x]; 23 First[x]=SIGN++; 24 } 25 26 void C_SEX() 27 { 28 int n,i; 29 scanf("%d",&n); 30 SEX[n]=1-SEX[n]; //改變性別 31 for(i=First[n];i!=0;i=ID[i].Next) //查找與該點相關的點 32 { 33 if(SEX[ID[i].TO]==SEX[n]) //與修改后的性別一樣， 34 { //說明之前是加上該點的權值， 35 sum-=ID[i].Vlaue; //減去該點的權值 36 } 37 else 38 { //與修改后的性別不一樣 39 sum+=ID[i].Vlaue; //說明之前是沒有加上該點的權值， 40 } //現在就加上該點的權值 41 } 42 return ; 43 } 44 void C_Map() 45 { 46 int x, y, z,i,Begin=0; 47 scanf("%d %d %d",&x,&y,&z); 48 for(i=First[x];i!=0;i=ID[i].Next)//查找是否已經存在的關系 49 { 50 if(ID[i].TO==y)//存在關系 51 { 52 Begin=ID[i].Vlaue; 53 ID[i].Vlaue=z; 54 break; 55 } 56 } 57 if(i!=0) 58 { 59 for(i=First[y];i!=0;i=ID[i].Next)//查找是否已經存在的關系 60 { 61 if(ID[i].TO==x)//存在關系 62 { 63 ID[i].Vlaue=z; 64 break; 65 } 66 } 67 } 68 else if(i==0)//如果沒有存在關系，創建兩個點 69 { 70 Add_E(x,y,z); 71 Add_E(y,x,z); 72 } 73 if(SEX[x]!=SEX[y])//如果性別不一樣，減去之前權值，加上當前的權值 74 sum+=(z-Begin); 75 76 return ; 77 } 78 79 void FIND()//輸出答案 80 { 81 printf("%lld\n",sum); 82 return ; 83 } 84 void work() 85 { 86 int N; 87 scanf("%d",&N); 88 switch(N) 89 { 90 case 1:C_SEX();break; 91 case 2:C_Map();break; 92 case 3:FIND();break; 93 } 94 return ; 95 } 96 int main() 97 { 98 int T,i,t; 99 int N,M,Q; 100 int x,y,z; 101 scanf("%d",&T); 102 t=1; 103 while(T--) 104 { 105 scanf("%d %d %d",&N,&M,&Q); 106 SIGN=1;sum=0; 107 for(i=1;i<=N;i++) 108 { 109 scanf("%d",&SEX[i]); 110 First[i]=0; 111 } 112 for(i=1;i<=M;i++) 113 { 114 scanf("%d %d %d",&x,&y,&z); 115 Add_E(x,y,z); 116 Add_E(y,x,z); 117 if(SEX[x]!=SEX[y])sum+=z; //判斷性別不一樣相加 118 } 119 printf("Case #%d:\n",t++); 120 while(Q--) 121 { 122 work(); 123 } 124 } 125 return 0; 126 } View Code

?

1 /*按照鏈表的邊數記錄*/ 2 #include <iostream> 3 #include <stdio.h> 4 #include <string.h> 5 #define MAX 100010 6 using namespace std; 7 int Len; //人數 8 int SEX[100010]; //性別 9 typedef struct edge 10 { 11 int TO; //下一個頂點 12 int Next; //記錄下一條邊的編號 13 int Vlaue; //權值 14 }EDGE; 15 EDGE ID[3*MAX]; //邊表,坑爹的邊數記得多弄些，不然有可能會TLE 16 int First[MAX]; //First[x]：x表示頭結點為x，First[x]表示下一條邊的編號 17 int SIGN; 18 long long sum; 19 void Add_E(int x,int y,int z) //添加邊 20 { 21 if(SEX[x]!=SEX[y])sum+=z; //判斷性別不一樣相加 22 ID[SIGN].TO=y; 23 ID[SIGN].Vlaue=z; 24 ID[SIGN].Next=First[x]; 25 First[x]=SIGN++; 26 } 27 28 void C_SEX() 29 { 30 int n,i; 31 scanf("%d",&n); 32 SEX[n]=1-SEX[n]; //改變性別 33 for(i=First[n];i!=0;i=ID[i].Next) //查找與該點相關的點 34 { 35 if(SEX[ID[i].TO]==SEX[n]) //與修改后的性別一樣， 36 { //說明之前是加上該點的權值， 37 sum-=ID[i].Vlaue*2; //減去該點的權值（無向圖） 38 } 39 else 40 { //與修改后的性別不一樣 41 sum+=ID[i].Vlaue*2; //說明之前是沒有加上該點的權值， 42 } //現在就加上該點的權值（無向圖） 43 44 } 45 } 46 void C_Map() 47 { 48 int x, y, z,i; 49 scanf("%d %d %d",&x,&y,&z); 50 for(i=First[x];i!=0;i=ID[i].Next)//查找是否已經存在的關系 51 { 52 if(ID[i].TO==y)//存在關系 53 { 54 if(SEX[x]!=SEX[y])//如果性別不一樣，減去之前權值，加上當前的權值 55 sum+=(z-ID[i].Vlaue); 56 ID[i].Vlaue=z; 57 break; 58 } 59 } 60 if(i!=0) 61 { 62 for(i=First[y];i!=0;i=ID[i].Next)//查找是否已經存在的關系 63 { 64 if(ID[i].TO==x)//存在關系 65 { 66 if(SEX[x]!=SEX[y])//如果性別不一樣，減去之前權值，加上當前的權值 67 sum+=(z-ID[i].Vlaue); 68 ID[i].Vlaue=z; 69 break; 70 } 71 } 72 } 73 else if(i==0)//如果沒有存在關系，創建兩個點 74 { 75 Add_E(x,y,z); 76 Add_E(y,x,z); 77 } 78 79 } 80 81 void FIND()//輸出答案 82 { 83 printf("%lld\n",sum/2);//無向圖，所以/2； 84 } 85 void work() 86 { 87 int N; 88 scanf("%d",&N); 89 switch(N) 90 { 91 case 1:C_SEX();break; 92 case 2:C_Map();break; 93 case 3:FIND();break; 94 } 95 } 96 int main() 97 { 98 int T,i,t; 99 int N,M,Q; 100 int x,y,z; 101 scanf("%d",&T); 102 t=1; 103 while(T--) 104 { 105 scanf("%d %d %d",&N,&M,&Q); 106 Len=N;SIGN=1;sum=0; 107 for(i=1;i<=N;i++) 108 { 109 scanf("%d",&SEX[i]); 110 First[i]=0; 111 } 112 for(i=1;i<=M;i++) 113 { 114 scanf("%d %d %d",&x,&y,&z); 115 Add_E(x,y,z); 116 Add_E(y,x,z); 117 } 118 printf("Case #%d:\n",t++); 119 for(i=0;i<Q;i++) 120 { 121 work(); 122 } 123 } 124 return 0; 125 } View Code

?

?

轉載于:https://www.cnblogs.com/Wurq/p/4463080.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的2015 编程之美 八卦的小冰的全部內容，希望文章能夠幫你解決所遇到的問題。

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