hdu 2121 Ice_cream’s world II
Ice_cream’s world II
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9250 Accepted Submission(s): 2481
Problem Description
After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.
Input
Every case have two integers N and M (N<=1000, M<=10000), the cities numbered 0…N-1, following M lines, each line contain three integers S, T and C, meaning from S to T have a road will cost C.
Output
If no location satisfy the queen’s require, you must be output “impossible”, otherwise, print the minimum cost in this project and suitable city’s number. May be exist many suitable cities, choose the minimum number city. After every case print one blank.
Sample Input
3 1
0 1 1
4 4
0 1 10
0 2 10
1 3 20
2 3 30
Sample Output
impossible
40 0
Ice_cream世界第二
问题描述
将土地授予ACMers后，女王想选择一个城市作为她的首都。这是冰淇淋世界的一个重要事件，也是一个非常困难的问题，因为世界上有N个城市和M条道路，每条道路都是有方向的。威斯基是冰淇淋界的总工程师。女王要求维斯基必须找到一个合适的地点建立首都，美化道路，让资本可以访问每个城市，项目的成本尽可能少。如果威斯基不能满足王后的要求，他就会惩罚你。
输入
每个情况下有两个整数N和M (N<=1000, M<=10000)，城市编号0…N-1，在M行之后，每行包含三个整数S, T和C，意味着从S到T有一条道路将花费C。
输出
如果没有位置满足女王的要求，你必须输出“不可能”，否则，打印这个项目的最低成本和合适的城市的数字。可以存在许多适合的城市，选择最小数量的城市。在每个案例之后打印一个空白。
Sample Input
3 1
0 1 1
4 4
0 1 10
0 2 10
1 3 20
2 3 30
Sample Output
impossible
40 0
题意即求不定根最小树形图。
无定根的最小树形图，像网络流的超级源和超级汇一样加一个起点，用邻接表（n>1000）
n<1000用邻接矩阵
代码：
#include<iostream>
#include<string.h>
using namespace std;
const double g=10.0,eps=1e-9;
const int N=1000+10,maxn=40000+10,inf=0x3f3f3f3f;
int in[N],vis[N],Hash[N];
int pre[N];
int ans,ansnum;
struct edge
{
int u,v,w;
}e[maxn];
int dirmst(int root,int nv,int ne)
{
ans=0;
while(1)
{
memset(in,inf,sizeof in);
for(int i=0;i<ne;i++)
{
int u=e[i].u,v=e[i].v;
if(e[i].w<in[v]&&v!=u)
{
in[v]=e[i].w;//找最小入边
pre[v]=u;//记录前驱
if(u==root)
ansnum=i;
}
}
in[root]=0;
for(int i=0;i<nv;i++)
if(in[i]==inf)
return 0;//如果不能构成最小树形图
int cntnum=0;
memset(vis,-1,sizeof vis);
memset(Hash,-1,sizeof Hash);
for(int i=0;i<nv;i++)
{
ans+=in[i];
int v=i;
while(vis[v]!=i&&v!=root&&Hash[v]==-1)
vis[v]=i,v=pre[v];
if(v!=root&&Hash[v]==-1)//有环
{
for(int u=pre[v];u!=v;u=pre[u])
Hash[u]=cntnum;
Hash[v]=cntnum++;
}
}
if(cntnum==0)
return 1;//没有环
for(int i=0;i<nv;i++)
if(Hash[i]==-1)
Hash[i]=cntnum++;//缩点
for(int i=0;i<ne;i++)
{
int v=e[i].v;
e[i].u=Hash[e[i].u];//重新编号
e[i].v=Hash[e[i].v];
if(e[i].u!=e[i].v)e[i].w-=in[v];//因为前面已经将in[v]加到ans中了
}
nv=cntnum;
root=Hash[root];
}
return 1;
}
int main()
{
int n,m;
while(cin>>n>>m)
{
int sum=0;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
e[i].u=a;e[i].v=b;e[i].w=c;
sum+=c;
}
int s=m;
for(int i=0;i<n;i++)
{
e[s].u=n;
e[s].v=i;
e[s].w=sum+1;//为了只有一个节点与root相连
s++;
}
ansnum=0;
if(!dirmst(n,n+1,n+m)||ans>=2*sum+2)
cout<<"impossible"<<endl;
else
cout<<ans-sum-1<<" "<<ansnum-m<<endl;
cout<<endl;
}
return 0;
}