# kuangbin带你飞 生成树专题 ： 次小生成树; 最小树形图;生成树计数

2份模板

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 210;
const int INF = 0x3f3f3f3f;
bool vis[MAXN];
int cost[MAXN][MAXN];
int lowcost[MAXN];
int pre[MAXN],MAX[MAXN][MAXN];
bool used[MAXN][MAXN];

int prim(int cost[][MAXN],int n)
{
int ret = 0;
memset(vis,false,sizeof(vis));
memset(MAX,0,sizeof(MAX));
memset(used,false,sizeof(used));
vis[1] = true;
pre[1] = -1;
for (int i = 1 ; i <= n ; i++)
{
lowcost[i] = cost[1][i];
pre[i] = 1;
}
lowcost[1] = 0;
pre[1] = -1;
for (int i = 2 ; i <= n ; i++)
{
int mincost = INF;
int pos = -1;
for (int j = 1 ; j <= n ; j++)
{
if (!vis[j] && lowcost[j] < mincost)
{
mincost = lowcost[j];
pos = j;
}
}
if (pos == -1) return -1;
ret += mincost;
vis[pos] = true;
used[pos][pre[pos]] = used[pre[pos]][pos] = true;
for (int j = 1;  j <= n ; j++)
{
if (vis[j] && j != pos) MAX[j][pos] = MAX[pos][j] = max(MAX[j][pre[pos]],lowcost[pos]);
if (!vis[j] && lowcost[j] > cost[pos][j])
{
lowcost[j] = cost[pos][j];
pre[j] = pos;
}
}
}
return ret;
}

int calcusmst(int cost[][MAXN],int n,int mst)
{
int MIN = INF;
for (int i = 1 ; i <= n ; i++)
{
for (int j = i + 1 ; j <= n ; j++)
{
if (cost[i][j] < INF && !used[i][j])
{
if (MIN > mst + cost[i][j] - MAX[i][j])
MIN = mst + cost[i][j] - MAX[i][j];
}
}
}
return MIN;
}

int main()
{
// freopen("sample.txt","r",stdin);
int T;
scanf("%d",&T);
while (T--)
{
int N,M;
scanf("%d%d",&N,&M);
for (int i = 0 ; i <= N ; i++)
for (int j = 0 ; j <= N ; j++) cost[i][j] = i == j ? 0 : INF;
while (M--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
cost[u][v] = w;
cost[v][u] = w;
}
int ret = prim(cost,N);
int smst = calcusmst(cost,N,ret);
printf("%d %d\n",ret,smst);
}
return 0;
}

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 110;
const int MAXM = MAXN * MAXN;
const int INF = 0x3f3f3f3f;
struct node
{
int u,v,w;
bool key;
friend bool operator < (const node &a,const node &b)
{
return a.w < b.w;
}
}edge[MAXM];
int fa[MAXN];
int MAX[MAXN][MAXN];
int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int N,M;
struct Edge
{
int u,v,w;
};
vector<Edge>G[MAXN];
vector<int>res;

int kruskal(int N)
{
sort(edge,edge + M);
int ret = 0,cnt = 0;
for (int i = 0 ; i < M ; i++)
{
int fu = Find(edge[i].u);
int fv = Find(edge[i].v);
if (fu != fv)
{
fa[fv] = fu;
cnt++;
ret += edge[i].w;
edge[i].key = true;
}
if(cnt >= N - 1) break;
}
return ret;
}

void dfs(int u,int fa,int facost)
{
for (int i = 0 ; i < (int)res.size() ; i++)
{
int x = res[i];
MAX[x][u] = MAX[u][x] = max(MAX[fa][x],facost);
}
res.push_back(u);
for (int i = 0 ; i < (int)G[u].size(); i++)
{
int v = G[u][i].v;
if (v != fa)
{
dfs(v,u,G[u][i].w);
}
}
}

int main()
{
// freopen("sample.txt","r",stdin);
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&N,&M);
for (int i = 0 ; i <= N ; i++) fa[i] = i;
for (int i = 0 ; i < M ; i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
edge[i].key = false;
}
for (int i = 0 ; i <= N ; i++) G[i].clear();
int mst = kruskal(N);
for (int i = 0 ; i < M ; i++)
{
if (edge[i].key == false) continue;
Edge tmp;
tmp.u = edge[i].u;
tmp.v = edge[i].v;
tmp.w = edge[i].w;
G[edge[i].u].push_back(tmp);
tmp.v = edge[i].u;
tmp.u = edge[i].v;
G[edge[i].v].push_back(tmp);
}
memset(MAX,0,sizeof(MAX));
res.clear();
int smst = INF;
dfs(1,-1,0);
for (int i = 0 ; i < M ; i++)
{
if (!edge[i].key)
smst = min(smst,mst + edge[i].w - MAX[edge[i].u][edge[i].v]);
}
printf("%d %d\n",mst,smst);
}
return 0;
}

POJ 1679 The Unique MST

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 210;
const int INF = 0x3f3f3f3f;
bool vis[MAXN];
int cost[MAXN][MAXN];
int lowcost[MAXN];
int pre[MAXN],MAX[MAXN][MAXN];
bool used[MAXN][MAXN];

int prim(int cost[][MAXN],int n)
{
int ret = 0;
memset(vis,false,sizeof(vis));
memset(MAX,0,sizeof(MAX));
memset(used,false,sizeof(used));
vis[1] = true;
pre[1] = -1;
for (int i = 1 ; i <= n ; i++)
{
lowcost[i] = cost[1][i];
pre[i] = 1;
}
lowcost[1] = 0;
pre[1] = -1;
for (int i = 2 ; i <= n ; i++)
{
int mincost = INF;
int pos = -1;
for (int j = 1 ; j <= n ; j++)
{
if (!vis[j] && lowcost[j] < mincost)
{
mincost = lowcost[j];
pos = j;
}
}
if (pos == -1) return -1;
ret += mincost;
vis[pos] = true;
used[pos][pre[pos]] = used[pre[pos]][pos] = true;
for (int j = 1;  j <= n ; j++)
{
if (vis[j]) MAX[j][pos] = MAX[pos][j] = max(MAX[j][pre[pos]],lowcost[pos]);
if (!vis[j] && lowcost[j] > cost[pos][j])
{
lowcost[j] = cost[pos][j];
pre[j] = pos;
}
}
}
return ret;
}

int calcusmst(int cost[][MAXN],int n,int ret)
{
int MIN = INF;
for (int i = 1 ; i <= n ; i++)
{
for (int j = i + 1 ; j <= n ; j++)
{
if (cost[i][j] < INF && !used[i][j])
MIN = min(MIN,ret + cost[i][j] - MAX[i][j]);
}
}
if (MIN == INF) return -1;
return MIN;
}

int main()
{
int T,N,M;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&N,&M);
for (int i = 0 ; i <= N ; i++)
for (int j = 0 ; j <= N ; j++) cost[i][j] = i == j ? 0 : INF;
while (M--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
cost[u][v] = cost[v][u] = w;
}
int ret = prim(cost,N);
if (ret == -1)
{
printf("Not Unique!\n");
continue;
}
if (ret == calcusmst(cost,N,ret)) printf("Not Unique!\n");
else printf("%d\n",ret);
}
return 0;
}

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const double INF = 1e14;
const int MAXN = 1010;
struct point
{
int x,y;
int people;
}src[MAXN];
int N;
double edge[MAXN][MAXN];
int nearvex[MAXN];
double lowcost[MAXN];
double sum;
bool used[MAXN][MAXN];
bool vis[MAXN];
double MAX[MAXN][MAXN];

void prim(int v0)
{
sum = 0;
memset(used,false,sizeof(used));
memset(vis,false,sizeof(vis));
memset(MAX,0,sizeof(MAX));
for (int i = 1 ; i <= N ; i++)
{
lowcost[i] = edge[v0][i];
nearvex[i] = v0;
}
vis[v0] = true;
for (int i = 1 ; i <= N ; i++)
{
double MIN = INF;
int pos = -1;
for (int j = 1 ; j <= N ; j++)
{
if (!vis[j] && lowcost[j] < MIN)
{
MIN = lowcost[j];
pos = j;
}
}
if (pos != -1)
{
sum += MIN;
used[pos][nearvex[pos]] = used[nearvex[pos]][pos] = true;
vis[pos] = true;
for (int k = 1 ; k <= N ; k++)
{
if (vis[k] && k != pos)
{
MAX[pos][k] = MAX[k][pos] = max(lowcost[pos],MAX[k][nearvex[pos]]);
}
else if (!vis[k] && edge[pos][k] < lowcost[k])
{
lowcost[k] = edge[pos][k];
nearvex[k] = pos;
}
}
}
}
}

int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d",&N);
for (int i = 1 ; i <= N ; i++)scanf("%d%d%d",&src[i].x,&src[i].y,&src[i].people);
for (int i = 1 ; i <= N ; i++)
{
edge[i][i] = 0.0;
for (int j = i + 1 ; j <= N ; j++)
{
double dist = sqrt((src[j].x - src[i].x) * (src[j].x - src[i].x) +
(src[j].y - src[i].y) * (src[j].y - src[i].y));
edge[i][j] = edge[j][i] = dist;
}
}
prim(1);
double ret = -1.0;
for (int i = 1 ; i <= N ; i++)
{
for (int j = 1 ; j <= N ; j++)
{
if (i == j) continue;
if (used[i][j])
{
double tmp = 1.0 * (src[i].people + src[j].people) / (sum - edge[i][j]);
ret = max(tmp,ret);
}
else
{
double tmp = 1.0 * (src[i].people + src[j].people) / (sum - MAX[i][j]);
ret = max(ret,tmp);
}
}
}
printf("%.2lf\n",ret);
}
return 0;
}

HDU 10600 ACM Contest and Blackout

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 110;
const int MAXM = MAXN * MAXN;
const int INF = 0x3f3f3f3f;
struct node
{
int u,v,w;
bool key;
friend bool operator < (const node &a,const node &b)
{
return a.w < b.w;
}
}edge[MAXM];
int fa[MAXN];
int MAX[MAXN][MAXN];
int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int N,M;
struct Edge
{
int u,v,w;
};
vector<Edge>G[MAXN];
vector<int>res;

int kruskal(int N)
{
sort(edge,edge + M);
int ret = 0,cnt = 0;
for (int i = 0 ; i < M ; i++)
{
int fu = Find(edge[i].u);
int fv = Find(edge[i].v);
if (fu != fv)
{
fa[fv] = fu;
cnt++;
ret += edge[i].w;
edge[i].key = true;
}
if(cnt >= N - 1) break;
}
return ret;
}

void dfs(int u,int fa,int facost)
{
for (int i = 0 ; i < (int)res.size() ; i++)
{
int x = res[i];
MAX[x][u] = MAX[u][x] = max(MAX[fa][x],facost);
}
res.push_back(u);
for (int i = 0 ; i < (int)G[u].size(); i++)
{
int v = G[u][i].v;
if (v != fa)
{
dfs(v,u,G[u][i].w);
}
}
}

int main()
{
// freopen("sample.txt","r",stdin);
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&N,&M);
for (int i = 0 ; i <= N ; i++) fa[i] = i;
for (int i = 0 ; i < M ; i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
edge[i].key = false;
}
for (int i = 0 ; i <= N ; i++) G[i].clear();
int mst = kruskal(N);
for (int i = 0 ; i < M ; i++)
{
if (edge[i].key == false) continue;
Edge tmp;
tmp.u = edge[i].u;
tmp.v = edge[i].v;
tmp.w = edge[i].w;
G[edge[i].u].push_back(tmp);
tmp.v = edge[i].u;
tmp.u = edge[i].v;
G[edge[i].v].push_back(tmp);
}
memset(MAX,0,sizeof(MAX));
res.clear();
int smst = INF;
dfs(1,-1,0);
for (int i = 0 ; i < M ; i++)
{
if (!edge[i].key)
smst = min(smst,mst + edge[i].w - MAX[edge[i].u][edge[i].v]);
}
printf("%d %d\n",mst,smst);
}
return 0;
}

UVA 10462 Is There A Second Way Left?

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 110;
const int MAXM = 410;
const int INF = 0x3f3f3f3f;
struct node
{
int u,v,w;
bool key;
friend bool operator < (const node &a,const node &b)
{
return a.w < b.w;
}
}edge[MAXM];
int fa[MAXN];
int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int MAX[MAXN][MAXN];
int N,M;

vector<node>G[MAXN];
vector<int>res;

int kruskal(int N)
{
for (int i = 0 ; i <= N ; i++) fa[i] = i;
sort(edge,edge + M);
int cnt = 0,ret = 0;
bool flag = false;
for (int i = 0 ; i < M ; i++)
{
int fu = Find(edge[i].u);
int fv = Find(edge[i].v);
if (fv != fu)
{
fa[fv] = fu;
cnt++;
ret += edge[i].w;
edge[i].key = true;
}
if (cnt >= N - 1)
{
flag = true;
break;
}
}
if (flag) return ret;
return -1;
}

void dfs(int u,int fa,int precost)
{
for (int i = 0 ; i < (int)res.size() ; i++)
{
int x = res[i];
MAX[x][u] = MAX[u][x] = max(MAX[fa][x],precost);
}
res.push_back(u);
for (int i = 0 ; i < (int)G[u].size() ; i++)
{
int v = G[u][i].v;
if (v == fa) continue;
dfs(v,u,G[u][i].w);
}
}

int calcusmst(int N,int mst)
{
int ret = INF;
for (int i = 0 ; i < M ; i++)
{
if (edge[i].key == false)
{
ret = min(ret,mst + edge[i].w - MAX[edge[i].u][edge[i].v]);
}
}
return ret == INF ? -1 : ret;
}

int main()
{
// freopen("sample.txt","r",stdin);
int T,kase = 1;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&N,&M);
for (int i = 0 ; i < M ; i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
edge[i].key = false;
}
if (N == 1)
{
printf("Case #%d : No second way\n",kase++);
continue;
}
for (int i = 0 ; i <= N ; i++) G[i].clear();
int mst = kruskal(N);
if (mst == -1)
{
printf("Case #%d : No way\n",kase++);
continue;
}
for (int i = 0 ; i < M ; i++)
{
if (edge[i].key == false) continue;
int u = edge[i].u;
int v = edge[i].v;
node tmp;
tmp.u = u;
tmp.v = v;
tmp.w = edge[i].w;
G[u].push_back(tmp);
swap(tmp.v,tmp.u);
G[v].push_back(tmp);
}
res.clear();
memset(MAX,0,sizeof(MAX));
dfs(1,-1,0);
int smst = calcusmst(N,mst);
if (smst == -1)
{
printf("Case #%d : No second way\n",kase++);
}
else printf("Case #%d : %d\n",kase++,smst);
}
return 0;
}

___________________________________________________________________________________________________________________________________________________

http://alanyume.com/669.html

1->2       8,

1->3       8,

2->3       4,

3->2        3

const int MAXN = 1010;
const int MAXM = MAXN * MAXN;
const int INF = 0x3f3f3f3f;
typedef int type;

struct Edge
{
int u,v;
type w;
}edge[MAXM];
int pre[MAXN], id[MAXN], vis[MAXN], N,M;
type in[MAXN];

type Zhuliu(int root, int V, int E)
{
type ret = 0;
while(true)
{
//1.找最小入边
for(int i = 0; i < V; i++) in[i] = INF;
for(int i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
if(edge[i].w < in[v] && u != v) {pre[v] = u; in[v] = edge[i].w;}
}
for(int i = 0; i < V; i++)
{
if(i == root) continue;
if(in[i] == INF) return -1;//除了跟以外有点没有入边,则根无法到达它
}
//2.找环
int cnt = 0;
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
in[root] = 0;
for(int i = 0; i < V; i++) //标记每个环
{
ret += in[i];
int v = i;
while(vis[v] != i && id[v] == -1 && v != root)  //每个点寻找其前序点，要么最终寻找至根部，要么找到一个环
{
vis[v] = i;
v = pre[v];
}
if(v != root && id[v] == -1)//缩点
{
for(int u = pre[v]; u != v; u = pre[u]) id[u] = cnt;
id[v] = cnt++;
}
}
if(cnt == 0) break; //无环   则break
for(int i = 0; i < V; i++)
if(id[i] == -1) id[i] = cnt++;
//3.建立新图
for(int i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
edge[i].u = id[u];
edge[i].v = id[v];
if(id[u] != id[v]) edge[i].w -= in[v];
}
V = cnt;
root = id[root];
}
return ret;
}

POJ 3164 Command Network

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 110;
const int MAXM = MAXN * MAXN;
const double INF = 1e15;
typedef double type;
struct point
{
double x,y;
}src[MAXN];

struct Edge
{
int u,v;
type w;
}edge[MAXM];
int pre[MAXN], id[MAXN], vis[MAXN], N,M;
type in[MAXN];

double dis(point a, point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

type Zhuliu(int root, int V, int E)
{
type ret = 0;
while(true)
{
//1.找最小入边
for(int i = 0; i < V; i++) in[i] = INF;
for(int i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
if(edge[i].w < in[v] && u != v) {pre[v] = u; in[v] = edge[i].w;}
}
for(int i = 0; i < V; i++)
{
if(i == root) continue;
if(in[i] == INF) return -1;//除了跟以外有点没有入边,则根无法到达它
}
//2.找环
int cnt = 0;
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
in[root] = 0;
for(int i = 0; i < V; i++) //标记每个环
{
ret += in[i];
int v = i;
while(vis[v] != i && id[v] == -1 && v != root)  //每个点寻找其前序点，要么最终寻找至根部，要么找到一个环
{
vis[v] = i;
v = pre[v];
}
if(v != root && id[v] == -1)//缩点
{
for(int u = pre[v]; u != v; u = pre[u]) id[u] = cnt;
id[v] = cnt++;
}
}
if(cnt == 0) break; //无环   则break
for(int i = 0; i < V; i++)
if(id[i] == -1) id[i] = cnt++;
//3.建立新图
for(int i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
edge[i].u = id[u];
edge[i].v = id[v];
if(id[u] != id[v]) edge[i].w -= in[v];
}
V = cnt;
root = id[root];
}
return ret;
}

int main()
{
// freopen("sample.txt","r",stdin);
while (scanf("%d%d",&N,&M) != EOF)
{
for (int i = 0 ; i < N ; i++) scanf("%lf%lf",&src[i].x,&src[i].y);
for (int i = 0 ; i < M ; i++)
{
int u,v;
scanf("%d%d",&u,&v);
u--;v--;
edge[i].u = u;
edge[i].v = v;
if (edge[i].u == edge[i].v) edge[i].w = INF;
else edge[i].w = dis(src[u],src[v]);
}
type ans = Zhuliu(0,N,M);
if (ans == -1) puts("poor snoopy");
else printf("%.2f\n",ans);
}
return 0;
}

UVA 11183 Teen Girl Squad

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 1010;
const int MAXM = MAXN * MAXN;
const int INF = 0x3f3f3f3f;
typedef int type;

struct Edge
{
int u,v;
type w;
}edge[MAXM];
int pre[MAXN], id[MAXN], vis[MAXN], N,M;
type in[MAXN];

type Zhuliu(int root, int V, int E)
{
type ret = 0;
while(true)
{
//1.找最小入边
for(int i = 0; i < V; i++) in[i] = INF;
for(int i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
if(edge[i].w < in[v] && u != v) {pre[v] = u; in[v] = edge[i].w;}
}
for(int i = 0; i < V; i++)
{
if(i == root) continue;
if(in[i] == INF) return -1;//除了跟以外有点没有入边,则根无法到达它
}
//2.找环
int cnt = 0;
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
in[root] = 0;
for(int i = 0; i < V; i++) //标记每个环
{
ret += in[i];
int v = i;
while(vis[v] != i && id[v] == -1 && v != root)  //每个点寻找其前序点，要么最终寻找至根部，要么找到一个环
{
vis[v] = i;
v = pre[v];
}
if(v != root && id[v] == -1)//缩点
{
for(int u = pre[v]; u != v; u = pre[u]) id[u] = cnt;
id[v] = cnt++;
}
}
if(cnt == 0) break; //无环   则break
for(int i = 0; i < V; i++)
if(id[i] == -1) id[i] = cnt++;
//3.建立新图
for(int i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
edge[i].u = id[u];
edge[i].v = id[v];
if(id[u] != id[v]) edge[i].w -= in[v];
}
V = cnt;
root = id[root];
}
return ret;
}

int main()
{
// freopen("sample.txt","r",stdin);
int T,kase = 1;
scanf("%d",&T);
while (T--)
{
int N,M;
scanf("%d%d",&N,&M);
for (int i = 0 ; i < M ; i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
}
type ret = Zhuliu(0,N,M);
if (ret == -1) printf("Case #%d: Possums!\n",kase++);
else printf("Case #%d: %d\n",kase++,ret);
}
return 0;
}

HDU 2121 Ice_cream’s world II

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
//http://alanyume.com/669.html
/*

1->2       8,

1->3       8,

2->3       4,

3->2        3

using namespace std;
*/
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 1010;
const int MAXM = MAXN * MAXN;
const int INF = 0x3f3f3f3f;
typedef int type;

struct Edge
{
int u,v;
type w;
}edge[MAXM];
int pre[MAXN], id[MAXN], vis[MAXN], N,M,pos;
type in[MAXN];

type Zhuliu(int root, int V, int E)
{
type ret = 0;
while(true)
{
//1.找最小入边
for(int i = 0; i < V; i++) in[i] = INF;
for(int i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
if(edge[i].w < in[v] && u != v) {pre[v] = u; in[v] = edge[i].w; if (u == root) pos = i;}
// 因为在缩点的时候我们需要给每一个点进行从新编号，这样对于我们是很尴尬的，于是我们只能从边上下手咯，
//  我们在每次对点进行从新编号的时候记录下虚拟节点的出边编号
}
for(int i = 0; i < V; i++)
{
if(i == root) continue;
if(in[i] == INF) return -1;//除了跟以外有点没有入边,则根无法到达它
}
//2.找环
int cnt = 0;
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
in[root] = 0;
for(int i = 0; i < V; i++) //标记每个环
{
ret += in[i];
int v = i;
while(vis[v] != i && id[v] == -1 && v != root)  //每个点寻找其前序点，要么最终寻找至根部，要么找到一个环
{
vis[v] = i;
v = pre[v];
}
if(v != root && id[v] == -1)//缩点
{
for(int u = pre[v]; u != v; u = pre[u]) id[u] = cnt;
id[v] = cnt++;
}
}
if(cnt == 0) break; //无环   则break
for(int i = 0; i < V; i++)
if(id[i] == -1) id[i] = cnt++;
//3.建立新图
for(int i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
edge[i].u = id[u];
edge[i].v = id[v];
if(id[u] != id[v]) edge[i].w -= in[v];
}
V = cnt;
root = id[root];
}
return ret;
}

int main()
{
// freopen("sample.txt","r",stdin);
while (scanf("%d%d",&N,&M) != EOF)
{
type sum = 0;
int tot = 0;
for (int i = 0 ; i < M ; i++)
{
scanf("%d%d%d",&edge[tot].u,&edge[tot].v,&edge[tot].w);
edge[tot].u++;
edge[tot].v++;
sum += edge[tot].w;
tot++;
}
sum++;
for (int i = 1 ; i <= N ; i++)
{
edge[tot].u = 0;
edge[tot].v = i;
edge[tot].w = sum;
tot++;
}
// for (int i = 0 ; i < tot ; i++) printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].w);
type ret = Zhuliu(0,N + 1,tot);
if (ret == -1 || ret >= 2 * sum) printf("impossible\n");
else
{
int ans;
for (int i = 1 ; i <= N ; i++)
if (pre[i] == 0)
{
ans = i;
break;
}
printf("%d %d\n",ret - sum,pos - M);
}
puts("");
}
return 0;
}

HDU 4009 Transfer water

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 1010;
const int MAXM = MAXN * MAXN;
const int INF = 0x3f3f3f3f;
struct Edge
{
int u,v,next;
int cost;
}edge[MAXM];

int pre[MAXN],id[MAXN],visit[MAXN],in[MAXN];
int zhuliu(int root,int n,int m,Edge edge[])
{
int res = 0,u ,v;
while (true)
{
for (int i = 0 ; i < n ; i++) in[i] = INF;
for (int i = 0 ; i < m ; i++)
{
if (edge[i].u != edge[i].v && edge[i].cost < in[edge[i].v])
{
pre[edge[i].v] = edge[i].u;
in[edge[i].v] = edge[i].cost;
}
}
for (int i = 0 ; i < n ; i++)
if (i != root && in[i] == INF)
return -1; //no tree;
int tn = 0;
memset(id,-1,sizeof(id));
memset(visit,-1,sizeof(visit));
in[root] = 0;
for (int i = 0 ; i < n ; i++)
{
res += in[i];
v = i;
while (visit[v] != i && id[v] == -1 && v != root)
{
visit[v] = i;
v = pre[v];
}
if (v != root && id[v] == -1)
{
for (int u = pre[v] ; u != v ; u = pre[u])
id[u] = tn;
id[v] = tn++;
}
}
if (tn == 0) break;
for (int i = 0 ; i < n ; i++)
if (id[i] == -1) id[i] = tn++;
for (int i = 0 ; i < m ;)
{
v = edge[i].v;
edge[i].u = id[edge[i].u];
edge[i].v = id[edge[i].v];
if (edge[i].u != edge[i].v)
edge[i++].cost -= in[v];
else swap(edge[i],edge[--m]);
}
n = tn;
root = id[root];
}
return res;
}

int N,X,Y,Z;
struct node
{
int a,b,c;
}src[MAXN];

int main()
{
while (scanf("%d%d%d%d",&N,&X,&Y,&Z) != EOF)
{
if (N == 0 && X == 0 && Y == 0 && Z == 0) break;
int L = 0;
for (int i = 1 ; i <= N ; i++)
{
scanf("%d%d%d",&src[i].a,&src[i].b,&src[i].c);
edge[L].u = 0;
edge[L].v = i;
edge[L].cost = src[i].c * X;
L++;
}
for (int i = 1 ; i <= N ; i++)
{
int cnt ;
scanf("%d",&cnt);
for (int j = 0 ; j < cnt ; j++)
{
int x;
scanf("%d",&x);
if (x == i) continue;
edge[L].u = i;
edge[L].v = x;
if (src[i].c >= src[x].c)
edge[L++].cost = Y * (abs(src[x].a - src[i].a) + abs(src[x].b - src[i].b) + abs(src[x].c - src[i].c));
else edge[L++].cost = Z + Y * (abs(src[x].a - src[i].a) + abs(src[x].b - src[i].b) + abs(src[x].c - src[i].c));
}
}
int ret = zhuliu(0,N + 1,L,edge);
if (ret == -1) puts("poor XiaoA\n");
else printf("%d\n",ret);
}
return 0;
}

————————————----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念：

1、G的度数矩阵D[G]是一个n*n的矩阵，并且满足：当i≠j时,dij=0；当i=j时，dij等于vi的度数。

2、G的邻接矩阵A[G]也是一个n*n的矩阵， 并且满足：如果vi、vj之间有边直接相连，则aij=1，否则为0。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 20;
const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};
int N,M;
typedef long long type;
const long long MOD = 1e9;
int id[20][20];
char G[20][20];
int cas;
struct Matrix
{
type mat[MAXN][MAXN];
void init()
{
memset(mat,0,sizeof(mat));
}

type det(int n)
{
int sign = 0;
type ret = 1;
for (int i = 0 ; i < n ; i++)
{
for (int j = i + 1 ; j < n ; j++)
{
while(mat[j][i])
{
type tmp = mat[i][i] / mat[j][i];
for (int k = i ; k < n ; k++)
{
mat[i][k] = (mat[i][k] - tmp * mat[j][k]); // %MOD
swap(mat[i][k],mat[j][k]);
}
sign++;
}
}
if (mat[i][i] == 0) return 0;
ret = (ret * mat[i][i]);// % MOD
}
if (sign & 1) ret = -ret;
return ret;//(ret % MOD + MOD) % MOD;
}
}slover;

int g[MAXN][MAXN];

int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int N,M;
scanf("%d%d",&N,&M);
memset(g,0,sizeof(g));
while (M--)
{
int u,v;
scanf("%d%d",&u,&v);
u--;
v--;
g[u][v] = g[v][u] = 1;
}
slover.init();
for (int i = 0 ; i < N ; i++)
{
for (int j = 0 ; j < N ; j++)
{
if (i != j && g[i][j])
{
slover.mat[i][j] = -1;
slover.mat[i][i]++;
}
}
}
printf("%lld\n",slover.det(N - 1));
}
return 0;
}

UVA 10766 Organising the Organisation

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const double eps = 1e-8;
const int MAXN = 110;
int sgn(long double x)
{
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
else return 1;
}

long double b[MAXN][MAXN];
long double det(long double a[][MAXN],int n)
{
int i, j, k, sign = 0;
long double ret = 1;
for(i = 0 ; i < n ; i++)
for(j = 0 ; j < n ; j++)   b[i][j] = a[i][j];
for(i = 0;i < n;i++)
{
if(sgn(b[i][i]) == 0)
{
for(j = i + 1 ; j < n ; j++)
if(sgn(b[j][i]) != 0)   break;
if(j == n)return 0;
for(k = i ; k < n ; k++)
swap(b[i][k],b[j][k]);
sign++;
}
ret *= b[i][i];
for(k = i + 1 ; k < n ; k++)
b[i][k] /= b[i][i];
for(j = i + 1 ; j < n ; j++)
for(k = i + 1 ; k < n ; k++)
b[j][k] -= b[j][i]*b[i][k];
}
if(sign & 1)ret = -ret;
return ret;
}

long double a[MAXN][MAXN];
int g[MAXN][MAXN];

int main()
{
int n,m,k;
while (scanf("%d%d%d",&n,&m,&k) != EOF)
{
memset(g,0,sizeof(g));
while (m--)
{
int u,v;
scanf("%d%d",&u,&v);
u--;v--;
g[u][v] = g[v][u] = 1;
}
memset(a,0,sizeof(a));
for (int i = 0 ; i < n ; i++)
for (int j = 0 ; j < n ; j++)
{
if (i != j && g[i][j] == 0)
{
a[i][i]++;
a[i][j] = -1;
}
}
double ans = det(a,n - 1);
printf("%.0lf\n",ans);
}
return 0;
}

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 250;
int N;
typedef long long type;
type MOD;
struct Matrix
{
type mat[MAXN][MAXN];
void init()
{
memset(mat,0,sizeof(mat));
}

type det(int n)
{
int sign = 0;
type ret = 1;
for (int i = 0 ; i < n ; i++)
{
for (int j = i + 1 ; j < n ; j++)
{
while(mat[j][i])
{
type tmp = mat[i][i] / mat[j][i];
for (int k = i ; k < n ; k++)
{
mat[i][k] = (mat[i][k] - tmp * mat[j][k]) % MOD;
swap(mat[i][k],mat[j][k]);
}
sign++;
}
}
if (mat[i][i] == 0) return 0;
ret = (ret * mat[i][i]) % MOD;
}
if (sign & 1) ret = -ret;
return (ret % MOD + MOD) % MOD;
}
}slover;

int main()
{
while (scanf("%d%lld",&N,&MOD) != EOF)
{
for (int i = 0 ; i < N ; i++)
for (int j = 0 ; j < N ; j++) scanf("%lld",&slover.mat[i][j]);
printf("%lld\n",slover.det(N));
}
return 0;
}

URAL 1627 Join

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 150;
const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};
int N,M;
typedef long long type;
const long long MOD = 1e9;
int id[20][20];
char G[20][20];
int cas;
struct Matrix
{
type mat[MAXN][MAXN];
void init()
{
memset(mat,0,sizeof(mat));
}

type det(int n)
{
int sign = 0;
type ret = 1;
for (int i = 0 ; i < n ; i++)
{
for (int j = i + 1 ; j < n ; j++)
{
while(mat[j][i])
{
type tmp = mat[i][i] / mat[j][i];
for (int k = i ; k < n ; k++)
{
mat[i][k] = (mat[i][k] - tmp * mat[j][k]) % MOD;
swap(mat[i][k],mat[j][k]);
}
sign++;
}
}
if (mat[i][i] == 0) return 0;
ret = (ret * mat[i][i]) % MOD;
}
if (sign & 1) ret = -ret;
return (ret % MOD + MOD) % MOD;
}
}slover;

int g[MAXN][MAXN];

int main()
{
while (scanf("%d%d",&N,&M) != EOF)
{
cas = 0;
for (int i = 0 ; i < N ; i++) scanf("%s",G[i]);
memset(id,-1,sizeof(id));
for (int i = 0 ; i < N ; i++)
{
for (int j = 0 ; j < M ; j++)
{
if (G[i][j] == ‘.‘)  id[i][j] = cas++;
}
}
memset(g,0,sizeof(g));
for (int i = 0 ; i < N ; i++)
{
for (int j = 0 ; j < M ; j++)
{
if (id[i][j] != -1)
{
int l = id[i][j];
for (int d = 0 ; d < 4 ; d++)
{
int nx = i + dx[d];
int ny = j + dy[d];
if (nx >= 0 && nx < N && ny >= 0 && ny < M && id[nx][ny] != -1)
{
int r = id[nx][ny];
g[l][r] = g[r][l] = 1;
}
}
}
}
}
slover.init();
for (int i = 0 ; i < cas ; i++)
{
for (int j = 0 ; j < cas ; j++)
{
if (i != j && g[i][j])
{
slover.mat[i][j] = -1;
slover.mat[i][i]++;
}
}
}
printf("%I64d\n",slover.det(cas - 1));
}
return 0;
}

HDU 4305 Lighting

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MOD = 10007;
const int MAXN = 350;
int N,R;
typedef int type;
void ext_gcd(type a,type b,type &d, type &x,type &y)
{
if (b == 0) {d = a ; x = 1 ; y = 0;}
else {ext_gcd(b,a % b,d,y,x); y -= x * (a / b);}
}

type inv(type a,type n)
{
type d,x,y;
ext_gcd(a,n,d,x,y);
return d == 1 ? (x + n) % n : -1;
}

struct Matrix
{
type mat[MAXN][MAXN];
void init()
{
memset(mat,0,sizeof(mat));
}

type det(int n)
{
for (int i = 0 ; i < n ; i++)
for (int j = 0 ; j < n ; j++) mat[i][j] = (mat[i][j] % MOD + MOD) % MOD;
type ret = 1;
for (int i = 0 ; i < n ; i++)
{
for (int j = i ; j < n ; j++)
{
if (mat[j][i] != 0)
{
for (int k = i ; k < n ; k++) swap(mat[i][k],mat[j][k]);
if (i != j) ret = (-ret + MOD) % MOD;
break;
}
}
if (mat[i][i] == 0)
{
ret = -1;
break;
}
for (int j = i + 1 ; j < n ; j++)
{
// int mut = (mat[j][i] * INV[mat[i][i]]) % MOD;
int mut = (mat[j][i] * inv(mat[i][i],MOD)) % MOD;
for (int k = i ; k < n ; k++)
mat[j][k] = (mat[j][k] - (mat[i][k] * mut) % MOD + MOD) % MOD;
}
ret = (ret * mat[i][i]) % MOD;
}
return ret;
}
}slover;

struct point
{
int x,y;
point (int tx = 0,int ty = 0)
{
x = tx;
y = ty;
}

point operator - (const point &rhs) const
{
return point(x - rhs.x,y - rhs.y);
}

int operator ^ (const point &rhs) const
{
return x * rhs.y - y * rhs.x;
}
}src[MAXN];

struct Line
{
point s,e;
Line(){}
Line(point a,point b)
{
s = a;
e = b;
}
};

bool onseg(point p,Line L)
{
return
((L.s - p) ^ (L.e - p)) == 0 && (p.x - L.s.x) * (p.x - L.e.x) <= 0 && (p.y - L.s.y) * (p.y - L.e.y) <= 0;
}

type dist(point a,point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool judge(int a,int b)
{
if (dist(src[a],src[b]) > R * R) return false;
for (int i = 0 ; i < N ; i++)
{
if (i == a || i == b) continue;
if (onseg(src[i],Line(src[a],src[b]))) return false;
}
return true;
}

int g[MAXN][MAXN];

int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&N,&R);
for (int i = 0 ; i < N ; i++)  scanf("%d%d",&src[i].x,&src[i].y);
memset(g,0,sizeof(g));
for (int i = 0 ; i < N ; i++)
{
for(int j = i + 1 ; j < N ; j++)
{
if (judge(i,j)) g[i][j] = g[j][i] = 1;
}
}
slover.init();
for (int i = 0 ; i < N ; i++)
{
for (int j = 0 ; j < N ; j++)
{
if (i != j && g[i][j])
{
slover.mat[i][i]++;
slover.mat[i][j] = -1;
}
}
}
printf("%d\n",slover.det(N - 1) % MOD);
}
return 0;
}

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 20;
const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};
int N,M;
typedef long long type;
const long long MOD = 1e9;
int id[20][20];
char G[20][20];
int cas;
struct Matrix
{
type mat[MAXN][MAXN];
void init()
{
memset(mat,0,sizeof(mat));
}

type det(int n)
{
int sign = 0;
type ret = 1;
for (int i = 0 ; i < n ; i++)
{
for (int j = i + 1 ; j < n ; j++)
{
while(mat[j][i])
{
type tmp = mat[i][i] / mat[j][i];
for (int k = i ; k < n ; k++)
{
mat[i][k] = (mat[i][k] - tmp * mat[j][k]);
swap(mat[i][k],mat[j][k]);
}
sign++;
}
}
if (mat[i][i] == 0) return 0;
ret = (ret * mat[i][i]);
}
if (sign & 1) ret = -ret;
return ret;
}
}slover;

int g[MAXN][MAXN];

int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int N,M;
scanf("%d%d",&N,&M);
memset(g,0,sizeof(g));
while (M--)
{
int u,v;
scanf("%d%d",&u,&v);
u--;
v--;
g[u][v] = g[v][u] = 1;
}
slover.init();
for (int i = 0 ; i < N ; i++)
{
for (int j = 0 ; j < N ; j++)
{
if (i != j && g[i][j])
{
slover.mat[i][j] = -1;
slover.mat[i][i]++;
}
}
}
printf("%lld\n",slover.det(N - 1));
}
return 0;
}

HDU 4408 Minimum Spanning Tree

Kruskal算法的基本思想是，按照边长排序，然后不断将短边加入集合，最终一步如果能成功把n-1条边都加入同一个集合，则找到了最小生成树。在维护集合时，可以使用并查集来快速处理。

/*
*算法引入：
*给定一个含有N个结点M条边的无向图,求它最小生成树的个数t(G);
*
*算法思想：
*抛开“最小”的限制不看,如果只要求求出所有生成树的个数,是可以利用Matrix-Tree定理解决的;
*Matrix-Tree定理此定理利用图的Kirchhoff矩阵,可以在O(N3)时间内求出生成树的个数;
*
*kruskal算法：
*将图G={V,E}中的所有边按照长度由小到大进行排序,等长的边可以按照任意顺序;
*初始化图G’为{V,Ø},从前向后扫描排序后的边,如果扫描到的边e在G’中连接了两个相异的连通块,则将它插入G’中;
*最后得到的图G’就是图G的最小生成树;
*
*由于kruskal按照任意顺序对等长的边进行排序,则应该将所有长度为L0的边的处理当作一个阶段来整体看待;
*令kruskal处理完这一个阶段后得到的图为G0,如果按照不同的顺序对等长的边进行排序,得到的G0也是不同;
*虽然G0可以随排序方式的不同而不同,但它们的连通性都是一样的,都和F0的连通性相同(F0表示插入所有长度为L0的边后形成的图);
*
*在kruskal算法中的任意时刻,并不需要关注G’的具体形态,而只要关注各个点的连通性如何(一般是用并查集表示);
*所以只要在扫描进行完第一阶段后点的连通性和F0相同,且是通过最小代价到达这一状态的,接下去都能找到最小生成树;
*
*经过上面的分析,可以看出第一个阶段和后面的工作是完全独立的;
*第一阶段需要完成的任务是使G0的连通性和F0一样,且只能使用最小的代价;
*计算出这一阶段的方案数,再乘上完成后续事情的方案数,就是最终答案;
*
*由于在第一个阶段中,选出的边数是一定的,所有边的长又都为L0;
*所以无论第一个阶段如何进行代价都是一样的,那么只需要计算方案数就行了;
*此时Matrix-Tree定理就可以派上用场了,只需对F0中的每一个连通块求生成树个数再相乘即可;
*
*Matrix-Tree定理:
*G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值；
*n-1阶主子式就是对于r(1≤r≤n),将C[G]的第r行,第r列同时去掉后得到的新矩阵,用Cr[G]表示;
*
*算法举例：
*HDU4408(Minimum Spanning Tree)
*
*题目地址：
*http://acm.hdu.edu.cn/showproblem.php?pid=4408
*
*题目大意：
*给定一个含有N个结点M条边的无向图,求它最小生成树的个数,所得结果对p取模;
**/

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}

const int MAXN = 110;
const int MAXM = 1010;

struct Edges
{
int a,b,c;
bool operator<(const Edges & x)const
{
return c<x.c;
}
}edge[MAXM];

int n,m;
int mod;
LL f[MAXN],U[MAXN],vist[MAXN];//f,U都是并查集，U是每组边临时使用
LL G[MAXN][MAXN],C[MAXN][MAXN];//G顶点之间的关系，C为生成树计数用的Kirchhoff矩阵

vector<int>V[MAXN];//记录每个连通分量

int Find(int x,LL f[])
{
if(x==f[x])
return x;
else
return Find(f[x],f);
}

LL det(LL a[][MAXN],int n)//生成树计数:Matrix-Tree定理
{
for(int i = 0; i < n ; i++)
for(int j = 0; j < n ; j++)
a[i][j] %= mod;
int ret = 1;
for(int i = 1 ; i < n ; i++)
{
for(int j = i + 1 ; j < n ; j++)
while(a[j][i])
{
int t = a[i][i] / a[j][i];
for(int k = i ; k < n ; k++)
a[i][k] = (a[i][k] - a[j][k] * t) % mod;
for(int k = i ; k < n ; k++)
swap(a[i][k],a[j][k]);
ret = -ret;
}
if(a[i][i] == 0)
return 0;
ret = ret * a[i][i] % mod;
}
return (ret + mod) % mod;
}

void Solve()
{
sort(edge,edge + m);//按权值排序
for(int i = 1 ; i <= n ; i++)//初始化并查集
{
f[i] = i;
vist[i] = 0;
}

LL Edge = -1;//记录相同的权值的边
LL ans = 1;
for(int k = 0 ; k <= m ; k++)
{
if(edge[k].c != Edge || k == m)//一组相等的边,即权值都为Edge的边加完
{
for(int i = 1 ; i <= n ; i++)
{
if(vist[i])
{
LL u = Find(i,U);
V[u].push_back(i);
vist[i] = 0;
}
}
for(int i = 1 ; i <= n ; i++) //枚举每个连通分量
{
if(V[i].size() > 1)
{
for(int a = 1 ; a <= n ; a++)
for(int b = 1 ; b <= n ; b++)
C[a][b] = 0;
int len = V[i].size();
for(int a = 0 ; a < len ; a++) //构建Kirchhoff矩阵C
for(int b = a + 1 ; b < len ; b++)
{
int a1 = V[i][a];
int b1 = V[i][b];
C[a][b] = (C[b][a] -= G[a1][b1]);
C[a][a] += G[a1][b1];//连通分量的度
C[b][b] += G[a1][b1];
}
LL ret = (LL)det(C,len);
ans=(ans * ret) % mod;//对V中的每一个连通块求生成树个数再相乘
for(int a = 0 ; a < len ; a++)
f[V[i][a]] = i;
}
}
for(int i = 1 ; i <= n ; i++)
{
U[i] = f[i] = Find(i,f);
V[i].clear();
}
if(k == m)
break;
Edge = edge[k].c;
}

int a = edge[k].a;
int b = edge[k].b;
int a1 = Find(a,f);
int b1 = Find(b,f);
if(a1 == b1)
continue;
vist[a1] = vist[b1] = 1;
U[Find(a1,U)] = Find(b1,U);//并查集操作
G[a1][b1]++;
G[b1][a1]++;
}

int flag = 0;
for(int i = 2; i <= n&& !flag ; i++)
if(U[i] != U[i-1])
flag = 1;
if(m == 0)
flag = 1;
printf("%I64d\n",flag ? 0 : ans % mod);

}

int main()
{
while(scanf("%d%d%d",&n,&m,&mod) != EOF)
{
if (n == 0 && m == 0 && mod == 0) break;
memset(G,0,sizeof(G));
for(int i = 1 ; i <= n ; i++)
V[i].clear();
for(int i = 0 ; i < m ; i++)
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
Solve();
}
return 0;
}

## 「kuangbin带你飞」专题十八 后缀数组

layout: post title: 「kuangbin带你飞」专题十八 后缀数组 author: "luowentaoaa" catalog: true tags: - kuangbin - 字符串 - 后缀数组 传送门 倍增法 struct DA{ bool cmp(int *r,int a,int b,int l){ return r[a]==r[b]&&r[a+l]==r[b+l]; } int t1[maxn],t2[maxn],c[maxn]; int r

## 「kuangbin带你飞」专题十二 基础DP

layout: post title: 「kuangbin带你飞」专题十二 基础DP author: "luowentaoaa" catalog: true tags: mathjax: true - kuangbin - 动态规划 传送门 A.HDU1024 Max Sum Plus Plus 题意 给你N个数,然后你分成M个不重叠部分,并且这M个不重叠部分的和最大. 思路 动态规划最大m字段和,dp数组,dp[i][j]表示以a[j]结尾的,i个字段的最大和 两种情况:1.第a[j

## 「kuangbin带你飞」专题二十二 区间DP

layout: post title: 「kuangbin带你飞」专题二十二 区间DP author: "luowentaoaa" catalog: true tags: - kuangbin - 区间DP - 动态规划 传送门 B.LightOJ - 1422 Halloween Costumes 题意 按顺序参加舞会,参加一个舞会要穿一种衣服,可以在参加完一个舞会后套上另一个衣服再去参加舞会,也可以在参加一个舞会的时候把外面的衣服脱了,脱到合适的衣服,但是脱掉的衣服不能再穿,参加完

## 「kuangbin带你飞」专题二十 斜率DP

layout: post title: 「kuangbin带你飞」专题二十 斜率DP author: "luowentaoaa" catalog: true tags: mathjax: true - kuangbin - 动态规划 - 斜率DP 传送门 A.HDU - 3507 Print Article 题意 就是输出序列a[n],每连续输出的费用是连续输出的数字和的平方加上常数M 让我们求这个费用的最小值. 题解 概率DP的入门题,把我搞得要死要活的. 首先dp[i]表示输出前i

## 【kuangbin带你飞】 专题五 并查集

A:简单并查集 B:简单并查集 C:简单并查集 D:带权并查集.注意带权并查集要在路径压缩和合并两处地方与一般并查集不同. 见神图 E:经典食物链,见神图 F: G: H:带权并查集,见神图 I: J:带权并查集,带权并查集 见神图 K: L: M:并查集 N:判断是否是一棵树.并查集 神图: 膜拜bin神orz...

## [kuangbin带你飞]专题十六 KMP &amp; 扩展KMP &amp; Manacher :G - Power Strings POJ - 2406（kmp简单循环节）

[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher G - Power Strings POJ - 2406 题目: Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of

## 跟着chengyulala刷题之[kuangbin带你飞]之&#39;并查集&#39;专题/斜眼笑

[kuangbin带你飞] 专题1-23 https://vjudge.net/article/187 专题五 并查集 POJ 2236 Wireless Network  http://poj.org/problem?id=2236POJ 1611 The Suspects  http://poj.org/problem?id=1611HDU 1213 How Many Tables  http://acm.hdu.edu.cn/showproblem.php?pid=1213HDU 3038