首页 > ACM题库 > HDU-杭电 > HDU 4818-RP problem-数论-[解题报告]HOJ
2015
09-18

HDU 4818-RP problem-数论-[解题报告]HOJ

RP problem

问题描述 :

  As an ACMer, you must have heard of the legend of Ren Pin (RP), which means a person’s lucky degree. Neither can RP be created, nor eliminated without foundation. It can only be transferred from one person to another. Moreover, everyone has his social circle. It’s guaranteed that each person has at least one friend and he cannot be the friend of himself. The relationship is directed. In RP system, one’s RP is transferred from himself to all of his friends uniformly every day. For example, A has three friends, B, C and D and his current RP is 1. In tomorrow, 1/3 of his RP will be transferred to B, 1/3 to C and 1/3 to D and RP from those treat him as friends will be transferred to him as well.

  On the other hand, the god in charge of the RP system is tired of the transferring RP from one person to another every day. Making the assumption that the total amount of RP is 1, he wants to know whether there is a stable distribution in RP system, so that by reallocating the RP of each person, he can lighten his workload. Stable distribution means if the structure of social network keeps unchanged, no matter how many days pass by, everyone’s RP keeps unchanged. You will see an example as follows. For the ease of presentation, let “X->Y” denotes X takes Y as his friend. There are only three persons A, B and C in the world with A->B, B->C, C->A and C->B. If the current RPs of A, B, C are 0.2, 0.4, 0.4 respectively, then the RPs will still be 0.2, 0.4, 0.4 in tomorrow. It’s obviously that the distribution keeps unchanged no matter how many days pass by, so (0.2, 0.4, 0.4) is a stable distribution. However, if the current RPs of A, B, C are 0.3, 0.3, 0.4, respectively, then the RPs will be 0.2, 0.5, 0.3 in tomorrow, so (0.3, 0.3, 0.4) is not a stable distribution. The god wonders, for a given a social network, how many stable distributions exist?

  Furthermore, if there is one and only one stable distribution, your friend A, who is lack of luck, wants to know whether he can increase his RP by making one more new friend. More specifically, letting RP(A, G) be the RP of A in the stable distribution for a network G, the RP of A after adding A->X to G is RP(A, G \/ {A->X}). Your friend A wants to know if there exists a person X, such that RP(A, G \/ {A->X}) is strictly larger than RP(A, G). For example, there are four persons A, B, C, D in the world with A->B, B->C, C->A, D->A. The only one stable distribution is (1/3, 1/3, 1/3, 0). If A->D is added to the network, the stable distribution will be (2/5, 1/5, 1/5, 1/5) and 2/5 > 1/3, so A can increase his RP by making friend with D. If there are multiple qualifying persons, your friend A wants to know which one can increase his RP to the maximum extent.

输入:

The first line of input contains an integer T (T ≤ 50) indicating the number of datasets. Each dataset starts with two integers n and m (n ≤ 100, n ≤ m ≤ n*(n-1)), where n and m indicate the number of persons and the number of relationships, respectively. Next m lines describe the relationships in the social network. Each of these lines will contain two integers u and v (0 ≤ u, v < n), indicating u->v.

输出:

The first line of input contains an integer T (T ≤ 50) indicating the number of datasets. Each dataset starts with two integers n and m (n ≤ 100, n ≤ m ≤ n*(n-1)), where n and m indicate the number of persons and the number of relationships, respectively. Next m lines describe the relationships in the social network. Each of these lines will contain two integers u and v (0 ≤ u, v < n), indicating u->v.

样例输入:

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

样例输出:

INF
1 1
1 -1

//高斯消元法解线性方程组
//每一个方程都是 进==出
//Ai1 * x1 + Ai2 *x2 + Ai3 * x3 +...+ An-1 * xn-1 = xi;
//所以别的点流进==本点流出xi
//移项发现每个A[i][i]=-1;
//A[i][j]=1/d[j];d[j]为j点出度。
//n个方程解n个未知数。要么是唯一解,要么是无穷解。
//若是唯一解,则枚举所有A->j(j为与A无连接的点)
//可以发现,我们连接A->j之后,矩阵中改变的只是出度的只有A,
//所以改变的只有A[i][n-1](i为A指向的点)
//我们在重新计算的时候,只不过每次替换掉原来的第n-1列,前面都是不变的。
//所以我们可以将所有要枚举的列增加到A的增广矩阵中一起做阶梯化。
//这与单独计算的时候是等价的(阶梯化的过程中只考虑前n-1列,后面只是附和运算的)
//所以一次高斯消元就足够了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N = 300;
const int INF=0x7fffffff;
#define eps 1e-9
double A[N][N];
double x[N];
int g[N][N],d[N];
vector<int>edge[N];
int add[N];
bool Gauss(int equ,int var){
    int row,col;
    for(row=col=0;row<equ&&col<var;col++,row++){
        int max_r=row;
        for(int i=row+1;i<equ;i++){
            if(fabs(A[max_r][col])<fabs(A[i][col])){
                max_r=i;
            }
        }
        if(fabs(A[max_r][col])<eps)return 0;
        if(max_r!=row){
            for(int i=col;i<var;i++){
                swap(A[max_r][i], A[row][i]);
            }
        }
        for(int i=col+1;i<var;i++){//将col+1~var化简
            A[row][i]/=A[row][col];
        }
        A[row][col]=1;
        for(int i=row+1;i<equ;i++){
            if(fabs(A[i][col])<eps)continue;
            for(int j=col+1;j<var;j++){
                A[i][j]+=A[row][j]*(-A[i][col]);
            }
            A[i][col]=0;
        }
    }
    return 1;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        
        scanf("%d%d",&n,&m);
        
        for(int i=0;i<n;i++)
            edge[i].clear();
        memset(d,0,sizeof(d));
        memset(g,0,sizeof(g));
        memset(A, 0, sizeof(A));
        
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            if(u!=v)g[u][v]=1;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j&&g[i][j]==1){
                    d[i]++;
                    edge[j].push_back(i);
                }
            }
        }
        
        for(int i=0;i<n;i++){
            A[i][i]=-1;
            for(int j=0;j<edge[i].size();j++){//j->i
                int v=edge[i][j];
                if(i==v)continue;
                A[i][v]=1.0/d[v];
            }
        }
        for(int i=0;i<=n;i++)
            A[n-1][i]=1;
        
        int cnt=1;
        for(int i=0;i<n-1;i++){//枚举点
            if(g[n-1][i]==0){//连边
                for(int j=0;j<n;j++){
                    if(g[n-1][j]){//修改n-1指向的所有点
                        A[j][n+cnt]=1.0/(d[n-1]+1);
                    }
                    else A[j][n+cnt]=0;
                }
                A[i][n+cnt]=1.0/(d[n-1]+1);
                A[n-1][n+cnt]=1;
                add[cnt]=i;
                cnt++;
            }
        }
        if(!Gauss(n,n+cnt)){
            printf("INF\n");
        }
        else{
            int max_cnt=-1;
            double mmax=A[n-1][n]/A[n-1][n-1];
            for(int i=1;i<cnt;i++){
                if(A[n-1][n]/A[n-1][n+i]>mmax){
                    max_cnt=add[i];
                    mmax=A[n-1][n]/A[n-1][n+i];
                }
            }
            printf("%d %d\n",1,max_cnt);
        }
    }
    return 0;
}

参考:http://blog.csdn.net/u012936765/article/details/46966471