HDU - 4126 Genghis Khan the Conqueror
树形dp+MST
题目描述
Genghis Khan(成吉思汗)(1162-1227), also known by his birth name Temujin(铁木真) and temple name Taizu(元太祖), was the founder of the Mongol Empire and the greatest conqueror in Chinese history. After uniting many of the nomadic tribes on the Mongolian steppe, Genghis Khan founded a strong cavalry equipped by irony discipline, sabers and powder, and he became to the most fearsome conqueror in the history. He stretched the empire that resulted in the conquest of most of Eurasia. The following figure (origin: Wikipedia) shows the territory of Mongol Empire at that time.
Our story is about Jebei Noyan(哲别), who was one of the most famous generals in Genghis Khan’s cavalry. Once his led the advance troop to invade a country named Pushtuar. The knights rolled up all the cities in Pushtuar rapidly. As Jebei Noyan’s advance troop did not have enough soldiers, the conquest was temporary and vulnerable and he was waiting for the Genghis Khan’s reinforce. At the meantime, Jebei Noyan needed to set up many guarders on the road of the country in order to guarantee that his troop in each city can send and receive messages safely and promptly through those roads.
There were N cities in Pushtuar and there were bidirectional roads connecting cities. If Jebei set up guarders on a road, it was totally safe to deliver messages between the two cities connected by the road. However setting up guarders on different road took different cost based on the distance, road condition and the residual armed power nearby. Jebei had known the cost of setting up guarders on each road. He wanted to guarantee that each two cities can safely deliver messages either directly or indirectly and the total cost was minimal.
Things will always get a little bit harder. As a sophisticated general, Jebei predicted that there would be one uprising happening in the country sooner or later which might increase the cost (setting up guarders) on exactly ONE road. Nevertheless he did not know which road would be affected, but only got the information of some suspicious road cost changes. We assumed that the probability of each suspicious case was the same. Since that after the uprising happened, the plan of guarder setting should be rearranged to achieve the minimal cost, Jebei Noyan wanted to know the new expected minimal total cost immediately based on current information.
输入
There are no more than 20 test cases in the input.
For each test case, the first line contains two integers N and M (1<=N<=3000, 0<=M<=N×N), demonstrating the number of cities and roads in Pushtuar. Cities are numbered from 0 to N-1. In the each of the following M lines, there are three integers x i, y i and c i(c i<=10 7), showing that there is a bidirectional road between x i and y i, while the cost of setting up guarders on this road is c i. We guarantee that the graph is connected. The total cost of the graph is less or equal to 10 9.
The next line contains an integer Q (1<=Q<=10000) representing the number of suspicious road cost changes. In the following Q lines, each line contains three integers X i, Y i and C i showing that the cost of road (X i, Y i) may change to C i (C i<=10 7). We guarantee that the road always exists and C i is larger than the original cost (we guarantee that there is at most one road connecting two cities directly). Please note that the probability of each suspicious road cost change is the same.
输出
For each test case, output a real number demonstrating the expected minimal total cost. The result should be rounded to 4 digits after decimal point.
样例输入
3 3
0 1 3
0 2 2
1 2 5
3
0 2 3
1 2 6
0 1 6
0 0
样例输出
6.0000
Hint
The initial minimal cost is 5 by connecting city 0 to 1 and city 0 to 2. In the first suspicious case, the minimal total cost is increased to 6;
the second case remains 5; the third case is increased to 7. As the result, the expected cost is (5+6+7)/3 = 6.
题意
给你一个图，有q次询问，每次询问如果替换一条边后最小生成树的大小是多少，求q次询问的平均值。（要替换的边的权一定不小于原来边权，替换只在当前次询问有效）
思路
首先找到一颗最小生成树，之后当要替换的边不在最小生成树里的话，当前的最小生成树就直接是最小生成树的值。如果要替换的边在最小生成树里面的话，比如(u,v)边是要替换的边，将(u,v)删掉之后就会形成两个子树，就需要找出一条能连接这两个子树最小的那条边，那我们就可以实现处理出最小生成树上每条边的最小替换值。
dfs（u，fa，p）的含义为以u为跟的子树中所有节点v连接到节点p最短距离的边。所以dp[u][v]=dp[v][u]=min(dp[u][v],dfs(v,u,p));
而dfs的值由u的所有儿子v节点连接到p的最小值res=min(tmp,res);&&u节点到p节点的值取min得if(p!=fa)
res=min(res,G[u][p]); 这样得到的就是u为根节点的子树到p的最小值。。之后枚举p（1-n）可得替换i-j的边再次成MST需要dp[i][j]。
好题
3目运算符时间快&&关闭输入流确实比scanf快
#pragma GCC optimize(3,"Ofast","inline") //G++
#include<bits/stdc++.h>#define TEST freopen("C:\\Users\\hp\\Desktop\\ACM\\in.txt","r",stdin);
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fcout cout<<setprecision(4)<<fixedusing namespace std;
typedef long long ll;const int inf=0x3f3f3f3f;
const int INF=0x7fffffffffffffff;
const int mod=1e9+7;
const int maxn = 3e3+5;int n,m,q;
ll MST;
struct node
{int x,y,val;bool friend operator < (const node a,const node b){return a.val<b.val;}
} a[maxn*maxn];
int re[maxn],G[maxn][maxn],vis[maxn][maxn],dp[maxn][maxn];
vector<int>edge[maxn];
void add(int x,int y)
{vis[x][y]=vis[y][x]=1;edge[x].push_back(y);edge[y].push_back(x);
}
void init()
{MST=0;for(int i=1; i<=n; i++){edge[i].clear();re[i]=i;for(int j=1; j<=n; j++){dp[i][j]=G[i][j]=inf;vis[i][j]=0;}}for(int i=1; i<=m; i++){int x,y,val;cin>>x>>y>>val;x++,y++;G[x][y]=G[y][x]=val;a[i]=node{x,y,val};}
}
int fin(int x)
{return re[x]==x?x:re[x]=fin(re[x]);
}
void kruscal()
{sort(a+1,a+m+1);int cnt=0;for(int i=1; i<=m; i++){int xx=fin(a[i].x),yy=fin(a[i].y);if(xx!=yy){cnt++;re[xx]=yy;MST+=a[i].val;add(a[i].x,a[i].y);}if(cnt==n-1) break;}
}
int dfs(int u,int fa,int p)
{int res=inf;for(auto v:edge[u]){if(v==fa) continue;int tmp=dfs(v,u,p);res=min(tmp,res);dp[u][v]=dp[v][u]=min(dp[u][v],tmp);}if(p!=fa)res=min(res,G[u][p]);return res;
}
main()
{ios;while(cin>>n>>m&&(n||m)){init();kruscal();for(int i=1; i<=n; i++){dfs(i,0,i);}cin>>q;int tmp_q=q;ll ans=0;while(q--){int x,y,val;cin>>x>>y>>val;x++,y++;vis[x][y]?ans+=MST-G[x][y]+min(dp[x][y],val):ans+=MST;}fcout<<ans*1.0/tmp_q<<"\n";}
}
