题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4818
深深地补一个坑~~~
现场赛坑在这题了，TAT。。。。
今天把代码改了下，过掉了，TAT
很明显的高斯消元的模型。
现场一开始想的也大概是对的。
根据度可以得到n个方程，加起来为1是一个方程，有一个是多余的。 加起来就是n个方程。
只可能是无穷解和唯一解的情况。
现场是先求解一遍，然后枚举所有可以加的，不停做高斯消元。
但是因为高斯消元是O(n^3) 的， 再枚举的话就是n^4了。。。。
这样做明显应该超时的，HDU交了这样做也是TLE，，，现场被坑死，一直返回WA， 然后程序就改得不成样子了。。。
其实枚举那个可以省略。
因为改变的就是最后一列。
可以扩展矩阵，在后面多加几列。 然后变化之后，直接就得到了x(n-1)的值。
只需要做一次高斯消元。
代码君：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <math.h>
using namespace std; #define eps 1e-6
const int MAXN=;
double a[MAXN][MAXN],x[MAXN];
int equ,var; int Gauss()
{
int i,j,k,col,max_r;
for(k=,col=;k<equ&&col<var;k++,col++){
max_r = k;
for(i=k+;i<equ;i++)
if(fabs(a[i][col])>fabs(a[max_r][col]))
max_r = i;
if(fabs(a[max_r][col])<eps)return ; //无解,有*变元
if(k != max_r){
for(j=col;j<var;j++)
swap(a[k][j],a[max_r][j]);
swap(x[k],x[max_r]);
}
x[k]/=a[k][col];
for(j=col+;j<var;j++)a[k][j]/=a[k][col];
a[k][col] = ;
for(i=;i<equ;i++)
if(i!=k){
x[i] -= x[k]*a[i][k];
for(j=col+;j<var;j++)a[i][j]-=a[k][j]*a[i][col];
a[i][col]=;
}
}
return ;
} vector<int>vec[MAXN];
int g[MAXN][MAXN];
int du[MAXN];
int add[MAXN]; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i = ;i < n;i++)
vec[i].clear();
memset(g,,sizeof(g));
memset(du,,sizeof(du));
int u,v;
while(m--)
{
scanf("%d%d",&u,&v);
if(u == v)continue;
g[u][v] = ;
}
for(int i = ;i < n;i++)
{
for(int j = ;j < n;j++)
if(j != i && g[i][j])
{
du[i]++;
vec[j].push_back(i);
}
}
equ = var = n;
for(int i = ;i < n;i++)
x[i] = ;
memset(a,,sizeof(a));
for(int i = ;i < n;i++)
{
a[i][i] = -;
int sz = vec[i].size();
for(int j = ;j < sz;j++)
{
int v = vec[i][j];
if(i == v)continue;
a[i][v] = 1.0 / du[v];
}
}
for(int i = ;i < n;i++)
a[n-][i] = ;
x[n-] = ; for(int k = ;k < n-;k++)
if(g[n-][k] == )
{
for(int i = ;i < n-;i++)
{
if(g[n-][i])a[i][var] = 1.0/(du[n-]+);
else a[i][var] = ;
}
a[k][var] = 1.0/(du[n-]+);
a[n-][var] = ;
add[var] = k;
var++;
} if(!Gauss())
{
printf("INF\n");
continue;
}
double tt = x[n-];
double now = x[n-];
int ans = -;
for(int i = n;i < var;i++)
{
if(x[n-]/a[n-][i] > now)
{
ans = add[i];
now = x[n-]/a[n-][i];
}
}
printf("%d %d\n",,ans);
}
return ;
}