hdu 2121+4009 最小树形图

http://www.cppblog.com/RyanWang/archive/2010/01/25/106427.html

简单来说，就是有向的最小生成树：

1、每个点找其最小的入边In[v] ? 如果有除跟节点以外的点找不到入边,则无解 : 否则答案累加In[v]

2、看看有没有环 ? 无环则已经找到解,返回答案 : 将环缩点

3、重新构图,每条边[u->v]的权值减去In[v],然后重复第一步

模板题：

hdu 2121：

View Code

  1 #include<iostream>
  2 #include<cstring>
  3 const int N=1010;
  4 const int inf=10000000;
  5 using namespace std;
  6 
  7 struct Edge{
  8     int u,v,w;
  9 }edge[N*N];
 10 
 11 int n,m,ansi;
 12 int In[N];
 13 int visited[N],ID[N];
 14 int pre[N];
 15 
 16 //root表示根结点，n是顶点树，m是边数
 17 //最小树形图邻接表版本，三步走，找最小入弧，找有向环，缩环为点
 18 int Directed_MST(int root,int n,int m){
 19     int u,v,i,cnt=0;
 20     while(true){
 21         //找最小入边
 22         for(i=0;i<n;i++)In[i]=inf;
 23         for(i=0;i<m;i++){
 24             u=edge[i].u;
 25             v=edge[i].v;
 26             if(edge[i].w<In[v]&&u!=v){
 27                 pre[v]=u;//u->v;
 28                 if(u==root)//记录是root从哪一条边到有效点的（这个点就是实际的起点）
 29                     ansi=i;
 30                 In[v]=edge[i].w;
 31             }
 32         }
 33         for(i=0;i<n;i++){
 34             if(i==root)continue;
 35             if(In[i]==inf)return -1;//说明存在点没有入边
 36         }
 37         //找环
 38         int cntcode=0;
 39         memset(visited,-1,sizeof(visited));
 40         memset(ID,-1,sizeof(ID));
 41         In[root]=0;
 42         //标记每一个环
 43         for(i=0;i<n;i++){
 44             cnt+=In[i];
 45             v=i;
 46             while(visited[v]!=i&&ID[v]==-1&&v!=root){
 47                 visited[v]=i;
 48                 v=pre[v];
 49             }
 50             //说明此时找到一个环
 51             if(v!=root&&ID[v]==-1){
 52                 //表示这是找到的第几个环，给找到的环的每个点标号
 53                 for(u=pre[v];u!=v;u=pre[u]){
 54                     ID[u]=cntcode;
 55                 }
 56                 ID[v]=cntcode++;
 57             }
 58         }
 59         if(cntcode==0)break;//说明不存在环
 60         for(i=0;i<n;i++){
 61             if(ID[i]==-1)
 62                 ID[i]=cntcode++;
 63         }
 64         //缩点，重新标记
 65         for(i=0;i<m;i++){
 66             int v=edge[i].v;
 67             edge[i].u=ID[edge[i].u];
 68             edge[i].v=ID[edge[i].v];
 69             //说明原先不在同一个环
 70             if(edge[i].u!=edge[i].v){
 71                 edge[i].w-=In[v];
 72             }
 73         }
 74         n=cntcode;
 75         root=ID[root];
 76     }
 77     return cnt;
 78 }
 79 
 80 
 81 int main(){
 82     while(scanf("%d%d",&n,&m)!=EOF){
 83         int sum=0;//添加的虚根点到每个点的权值比所有真实权值总和大1
 84         for(int i=0;i<m;i++){
 85             scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
 86             sum+=edge[i].w;
 87         }
 88         sum++;
 89         for(int i=m;i<m+n;i++){
 90             edge[i].u=n;//加的虚根点
 91             edge[i].v=i-m;
 92             edge[i].w=sum;
 93         }
 94         int ans=Directed_MST(n,n+1,n+m);
 95         if(ans==-1||ans>=2*sum){
 96             printf("impossible\n");
 97         }else 
 98             printf("%d %d\n",ans-sum,ansi-m);
 99         printf("\n");
100     }
101     return 0;
102 }

hdu4009：

View Code

  1 #include<iostream>
  2 #include<cstring>
  3 const int N = 1010;
  4 const int inf=10000000;
  5 using namespace std;
  6 struct Point{
  7     int x,y,z;
  8 }p[N];
  9 
 10 struct Edge{
 11     int u,v,w;
 12 }edge[N*N];
 13 
 14 int X,Y,Z;
 15 int pre[N],ID[N],In[N],visited[N];
 16 
 17 //n表示点数，m表示边数，root表示根
 18  int Directed_MST(int root,int n,int m){
 19     int u,v,i,cnt=0;
 20     while(true)
 21     {
 22         for(i=0;i<n;i++)In[i]=inf;
 23         for(i=0;i<m;i++){
 24             u=edge[i].u;
 25             v=edge[i].v;
 26             if(edge[i].w<In[v]&&u!=v){
 27                 pre[v]=u;//找出每个点的最小入弧
 28                 In[v]=edge[i].w;
 29             }
 30         }
 31         //除根外有个节点无入弧，就返回false
 32         for(i=0;i<n;i++){
 33             if(i==root)continue;
 34             if(In[i]==inf)return -1;
 35         }
 36         In[root]=0;
 37         int cntcode=0;
 38         memset(ID,-1,sizeof(ID));
 39         memset(visited,-1,sizeof(visited));
 40         for(i=0;i<n;i++){
 41             cnt+=In[i];//进行缩圈
 42             v=i;
 43             while(visited[v]!=i&&ID[v]==-1&&v!=root){
 44                 visited[v]=i;
 45                 v=pre[v];
 46             }
 47             if(v!=root&&ID[v]==-1){
 48                 for(u=pre[v];u!=v;u=pre[u])
 49                     ID[u]=cntcode;
 50                 ID[v]=cntcode++;
 51             }
 52         }
 53         if(cntcode==0) break;
 54         for(i=0;i<n;i++){
 55             if(ID[i]==-1)
 56                 ID[i]=cntcode++;
 57         }
 58         for(i=0;i<m;i++){
 59             v=edge[i].v;//进行缩点，重新标记。
 60             edge[i].u=ID[edge[i].u];
 61             edge[i].v=ID[edge[i].v];
 62             if(edge[i].u!=edge[i].v)
 63                 edge[i].w-=In[v];
 64         }
 65         n=cntcode;
 66         root=ID[root];
 67     }
 68     return cnt;
 69 }
 70 
 71  int get_cost(Point& a,Point& b){
 72     int dis=abs(a.x-b.x)+abs(a.y-b.y)+abs(a.z-b.z);
 73     if(a.z>=b.z)
 74         return dis*Y;
 75     return dis*Y+Z;
 76 }
 77 
 78 int main()
 79 {
 80     int n,m,k,a;
 81     while(scanf("%d %d %d %d",&n,&X,&Y,&Z)==4 && (n||X||Y||Z)){
 82         m=0;
 83         for(int i=1;i<=n;i++)
 84             scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);
 85         for(int i=1;i<=n;i++){
 86             scanf("%d",&k);
 87             while(k--){
 88                 scanf("%d",&a);
 89                 edge[m].u=i;
 90                 edge[m].v=a;
 91                 edge[m++].w=get_cost(p[i],p[a]);
 92             }
 93         }
 94         for(int i=1;i<=n;i++){
 95             edge[m].u=0;
 96             edge[m].v=i;
 97             edge[m++].w=p[i].z*X;
 98         }
 99         printf("%d\n",Directed_MST(0,n+1,m));
100     }
101     return 0;
102 }