2015
09-18

# 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];
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;
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){
mmax=A[n-1][n]/A[n-1][n+i];
}
}
printf("%d %d\n",1,max_cnt);
}
}
return 0;
}

1. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

2. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

3. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

4. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

5. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

6. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

7. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

8. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

9. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

10. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

11. 哼，斗罗那唐三修炼的轻轻松松的，那萧炎呢，收服异火多痛苦，和爱人分离多难受，唐三的老婆就变成兔子而已居然还可以变回来，成神还就通过考验就好了，萧炎都要经过不知道多少次的来回生死门才称帝，唐三经过的生死门有多少？你们还骂斗破?傻不傻傻不傻。还有我看唐三的辛

12. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

13. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

14. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

15. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

16. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

17. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

18. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

19. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

20. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

21. AAAAA,①a的环手的动作在心理学上是一种防御性动作，她内心有所隐瞒。②相机在手腕上说明发生争执时在拍照，两个女孩子可能因为照片不和。③别人都说6点左右，A说的是6点多，说明她知道时间。

22. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

23. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

24. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

25. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

26. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

27. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

28. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

29. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

30. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

31. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。

32. 不能是、知识越高越不忠，收入越高越忘本，做人必须讲正义，没有良心算啥人。就算你是反对派，脱离大众有能耐。介石临终高评毛，不算伟人有胸怀。你们反毛是为谁，百姓心明亮如镜。