[UVA][矩陣] 11675 - Happy Friends
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 dth 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 dth day. But if his degree of happiness increased at dth 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 ith integer represents the degree of happiness of ith 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
|
Case 1:
1 0
|
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;
}