2014-03-02 14:02:47| 人氣1,319| 回應0 | 上一篇 | 下一篇

[UVA][矩陣] 11675 - Happy Friends

推薦 0 收藏 0 轉貼0 訂閱站台

Problem J
Happy Friends

Input: Standard Input

Output: Standard Output

The happiness of your friends makes you happier, and this increase of your happiness also has impact on your friends' happiness. What if no other effect (like dissatisfaction, poverty, enmity etc.) exits? The happiness would always increase day by day in a friendship network.

Can you help to analyze the scenario if only happiness exists in a friendship network? You are given a friendship network of N friends. You can identify them by integers from 0 to N - 1. You are also given M pairs of integer. Each pair represents a friendship between two persons in that network. You are also given a person who is the first happy person in the network. The initial degree of happiness of that first person is 1. Initial degree of happiness of all others in that friendship network is 0. The network will be given in such a way that each person’s degree of happiness will be affected after a certain period by the initial happy person.

Can you answer, what will be the degree of happiness of all of N persons in that network after D days if the degree of happiness of each person increases by a defined rule?

The only simple rule is - Each day, a person's degree of happiness is increased if and only if his degree of happiness is not increased in previous day. If the degree of happiness is not increased in previous day then it will increased by the summation of degree of happiness of all of his friends at previous day.

To make it more clear, let us consider a person p, and his degree of happiness is not increased at d^th day, so his degree of happiness will increase at (d+1)^th day by the summation of degree of happiness of all of his friends at d^th day. But if his degree of happiness increased at d^th day, it will remain same after (d+1)^th day.

Input

Input will start with an integer T(1 ≤ T ≤ 200), number of test cases. Each case starts with four integers N(1 ≤ N ≤ 30), M(N-1 ≤ M ≤ N*(N-1)/2), K(0 ≤ K ≤ N-1) and D(0 ≤ D ≤ 1000000000), number of nodes, number of friendships, initial happy person and number of days. Each of the next M lines will contain two integers u and v(0 ≤ u, v ≤ N-1, u≠v), which represents that u and v are friends.

Output

For each test case output a single line providing the case number followed by N space separated integers. The i^th integer represents the degree of happiness of i^th person after D days. The degree of happiness can be very large so that you should output the value of degree of happiness modulo 1000000007.

See sample input and output for exact format.

Sample Input Output for Sample Input

2
2 1 0 0
0 1
4 3 0 3
0 1
1 2
2 3

Case 1: 1 0
Case 2: 2 4 1 1

Problem setter: Arifuzzaman Arif

Special Thanks: Manzurur Rahman Khan

題目描述 :

每一天每個人都會將他的快樂分享給其他朋友。
如果這個人今天有獲得快樂，則下一天便不會增加。反之，亦然。 // 快樂值是累計的

問說有 N 個人，一開始從 K 號人傳送快樂，在 D 天后的快樂值為何。

題目解法 :

很明顯地，會有兩個轉移方程，會有兩批人馬輪流在每一天分享快樂。

因此先建造分層圖，將其分成兩類，然後把轉移方程求出。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MOD 1000000007
struct Matrix {
   int row, column;
   long long v[30][30];
   Matrix(int single, int r, int c) {
       memset(v, 0, sizeof(v));
       for(int i = 0; i < r && i < c; i++)
           v[i][i] = single;
       row = r, column = c;
   }
   void print() {
       for(int i = 0; i < row; i++) {
           printf("[");
           for(int j = 0; j < column; j++) {
               printf("%3d", v[i][j]);
           }
           puts("]");
       }
       puts("--");
   }
};
Matrix multiply(Matrix &x, Matrix &y) {
   Matrix ret(0, x.row, y.column);// x.column == y.row
   for(int i = 0; i < x.row; i++) {
       for(int j = 0; j < y.column; j++)
           for(int k = 0; k < x.column; k++) {
               ret.v[i][j] += x.v[i][k] * y.v[k][j];
               ret.v[i][j] %= MOD;
           }
   }
   return ret;
}
Matrix matrix_pow(Matrix x, int n) {
   Matrix ret(1, x.row, x.column);
   while(n) {
       if(n&1)
           ret = multiply(ret, x);
       x = multiply(x, x), n >>= 1;
   }
   return ret;
}
int level[30], g[30][30];
void buildLevelGraph(int N, int s) {
   memset(level, 0, sizeof(level));
   queue<int> Q;
   Q.push(s), level[s] = 1;
   while(!Q.empty()) {
       int tn = Q.front();
       Q.pop();
       for(int i = 0; i < N; i++) {
           if(g[tn][i] && level[i] == 0) {
               level[i] = level[tn] + 1;
               Q.push(i);
           }
       }
   }
}
int main() {
   int testcase, cases = 0;
   int N, M, K, D;
   int i, j, k, x, y;
   scanf("%d", &testcase);
   while(testcase--) {
       scanf("%d %d %d %d", &N, &M, &K, &D);
       memset(g, 0, sizeof(g));
       for(i = 0; i < M; i++) {
           scanf("%d %d", &x, &y);
           g[x][y] = g[y][x] = 1;
       }
       buildLevelGraph(N, K);
       Matrix odd(1, N, N), even(1, N, N);
       for(i = 0; i < N; i++) {
           for(j = 0; j < N; j++) {
               if(level[i]&1)
                   even.v[i][j] |= g[i][j];
               else
                   odd.v[i][j] |= g[i][j];
           }
       }
       Matrix oe = multiply(even, odd);
       Matrix ret = matrix_pow(oe, D/2);
       if(D&1)
           ret = multiply(odd, ret);
       printf("Case %d:", ++cases);
       for(i = 0; i < N; i++)
           printf(" %lld", ret.v[i][K]);
       puts("");
   }
   return 0;
}

我要檢舉

#11675#Happy Friends#矩陣

台長： Morris

您可能對以下文章有興趣

[UVA][Math] 11314 - Hardly Hard

d089. 145 - Gondwanaland Telecom

[UVA][匈牙利] 11363 - Cuckoo Hashing

[UVA][概率] 10217 - A Dinner with Schwarzenegger

人氣(1,319) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][DP] 11598 - Optimal Segments
此分類上一篇:[UVA][概率] 11680 - Dragster

回應(0)