7.8练习赛

阅读量：4984 次

发布时间：2019-06-12

本文共 8971 字，大约阅读时间需要 29 分钟。

7.8练习赛

A修公路

时间限制 : - MS 空间限制 : 65536 KB

评测说明 : 时限1000ms

问题描述

某岛国有n个小岛构成(编号1到n)，该国政府想要通过n-1条双向公路将这些小岛连接起来，使得任意两个岛屿之间都能相互到达。公路有两种，一种是高速公路，车速快，建设花费大；另一种是普通公路，车速慢，建设花费少。该国政府不想在一条公路上花费过多的钱，但又要求修建的公路中至少有k条高速公路。所以政府希望，在满足上述条件的情况下，使得最贵的一条公路花费尽可能少，请你帮忙计算出其中最贵一条公路的价格。

输入格式

第一行，三空格间隔的整数n,k,m，其中m表示有m对岛屿间可以修路。

接下来以下的m行，每行四个正整数a,b,c1,c2 表示在岛屿a与b 之间修高速公路花费c1块钱,修普通公路,花费c2块钱。

输出格式

一个整数表示最贵那条公路的费用。

样例输入 1

4 2 4

1 2 6 5

1 3 3 1

2 4 6 1

3 4 4 2

样例输出 1

样例输入 2

4 1 5

1 2 6 5

1 3 3 1

2 3 9 4

2 4 6 1

3 4 4 3

样例输出 2

样例输入 3

10 4 19

3 9 6 3

1 3 4 1

5 3 10 2

8 9 8 7

6 8 8 3

7 1 3 2

4 9 9 5

10 8 9 1

2 6 9 1

6 7 9 8

2 6 2 1

3 8 9 5

3 2 9 6

1 6 10 3

5 6 3 1

2 7 6 1

7 8 6 2

10 9 2 1

7 1 10 2

样例输出 3

提示

对于30%的数据， 1<=n<=1000 0<=k<=10 n-1<=m<=3000

对于100%的数据，1<=n<=10000 0<=k<=n-1 n-1<=m<=20000

二分答案+最少生成树思想

二分生成树的最大边权mid，判断这样的生成树是否存在就行了

每次判断时分成两步走，首先讨论高速公路，选用的高速公路边权小于等于mid，能加的边都加进去

判断生成树中的树边个数是否小于等于k，若小于k，表明这个生成树不存在。

再讨论普通公路，能加进去的边都加进去，加完边后判断生成树的树边是不是n-1

（生成树联通了所有的点），若不是，表明这个生成树不存在。

老板代码

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 inline int read() 6 { 7     int x=0;char ch=getchar(); 8     while(ch<'0'||ch>'9')ch=getchar(); 9     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}10     return x;11 }12 int n,K,m,ans;13 int fa[10005];14 struct data{
    int x,y,c1,c2;}e[20005];15 int find(int x)16 {
    return x==fa[x]?x:fa[x]=find(fa[x]);}17 bool jud(int x)18 {19     for(int i=1;i<=n;i++)fa[i]=i;20     int cnt=0;21     for(int i=1;i<=m;i++)22     {23         if(e[i].c1>x)continue;24         int p=find(e[i].x),q=find(e[i].y);25         if(p!=q)26         {fa[p]=q;cnt++;}27     }28     if(cnt
         
          x)continue;32         int p=find(e[i].x),q=find(e[i].y);33         if(p!=q)34         {fa[p]=q;cnt++;}35     }36     if(cnt!=n-1)return 0;37     return 1;38 }39 int main()40 {41     freopen("road.in","r",stdin);42     freopen("road.out","w",stdout);43     n=read(),K=read(),m=read();44     for(int i=1;i<=m;i++)45         e[i].x=read(),e[i].y=read(),e[i].c1=read(),e[i].c2=read();46     int l=1,r=30000;47     while(l<=r)48     {49         int mid=(l+r)>>1;50         if(jud(mid)){ans=mid;r=mid-1;}51         else {l=mid+1;}52     }53     printf("%d",ans);54     return 0;55 }

自己的：

1 #include
      
        2 #include
       
         3 using namespace std; 4 int father[10005]; 5 struct ztcakioi 6 { 7     int a,b,gao,pu; 8 }; 9 int n,k,m,L=1,R=2000005,mid;10 ztcakioi edge[20005];11 int read()12 {13     int x=0;14     char c=getchar();15     while(c<'0'||c>'9')c=getchar();16     while(c>='0'&&c<='9')17     {18         x=(x<<1)+(x<<3)+c-'0';19         c=getchar();20     }21     return x;22 }23 int getfather(int p)24 {25     if(father[p]!=p)father[p]=getfather(father[p]);26     return father[p];27 }28 bool Kruskal(int ans)29 {30     int i,x,y,cnt=0;31     for(int i=1; i<=n; i++)father[i]=i;32     for(int i=1; i<=m&&cnt
        
         ans)continue; //超过ztcakioi二分结果，返回 35         x=edge[i].a;36         y=edge[i].b;37         x=getfather(x);38         y=getfather(y);39         if(x==y)continue;40         father[x]=y;41         cnt++;//ztcakioi 次数+1 42     }43     if(cnt
         
          ans)continue;//超过ztcakioi二分结果，返回 47         x=edge[i].a;48         y=edge[i].b;49         x=getfather(x);50         y=getfather(y);51         if(x==y)continue;52         father[x]=y;53         cnt++;54     }55     if(cnt==n-1)return true;//ztcak了全部赛事 56     return false;57 }58 int main()59 {60     ios::sync_with_stdio(false);61     cout.tie(NULL);62     n=read(),k=read(),m=read();63     for(int i=1; i<=m; i++)64     {65         edge[i].a=read(),edge[i].b=read(),edge[i].gao=read(),edge[i].pu=read();66     }67     while(L<=R)//二分68     {69         mid=(L+R)/2;70         if(Kruskal(mid))R=mid-1;71         else L=mid+1;72     }73     cout<

B【USACO 2015 Jan Gold】牧草鉴赏家

时间限制 : 10000 MS 空间限制 : 65536 KB

问题描述

约翰有n块草场，编号1到n，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。

贝西总是从1号草场出发，最后回到1号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。问，贝西最多能吃到多少个草场的牧草。

输入格式

第一行，两个整数N和M(1<=N,M<=100000)

接下来M行，表示有M条单向道路，每条道路有连个整数X和Y表示，从X出发到达Y。

输出格式

一个整数，表示所求答案

样例输入

7 10

1 2

3 1

2 5

2 4

3 7

3 5

3 6

6 5

7 2

4 7

样例输出

提示

贝西的行走线路是1, 2, 4, 7, 2, 5, 3, 1 ，在5到3的时候逆行了一次。

题意：

给一个有向图，然后选一条路径起点终点都为1的路径出来，有一次机会可以沿某条边逆方向走，

问最多有多少个点可以被经过？（一个点在路径中无论出现多少次(≥1)对答案的贡献均为1）

题解：

首先强连通分量缩点。

然后形成了dfs统计出：

集合A：点 1 能到哪些点,

集合B：哪些点能到点 1

然后这两个集合各为拓扑图。

现在一条从1出发，最后又回到1的最长路径就可以被表示为

1~A中某点a最长链+此点通过逆向边直接回到集合B中某点b后1~b的最长链。

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #define N 200003 8 using namespace std; 9 int n,m; 10 int point[N],v[N],Next[N],x[N],y[N],dis[N],dis1[N],can[N]; 11 int belong[N],size[N],st[N],top,tot,cnt,sz,dfsn[N],ins[N],low[N]; 12 void add(int x,int y) 13 { 14 tot++; 15 Next[tot]=point[x]; 16 point[x]=tot; 17 v[tot]=y; 18 19 } 20 void tarjan(int x) 21 { 22 dfsn[x]=low[x]=++sz; 23 st[++top]=x; 24 ins[x]=1; 25 for (int i=point[x]; i; i=Next[i]) 26 if (!dfsn[v[i]]) 27 { 28 tarjan(v[i]); 29 low[x]=min(low[x],low[v[i]]); 30 } 31 else if (ins[v[i]]) low[x]=min(low[x],dfsn[v[i]]); 32 if (dfsn[x]==low[x]) 33 { 34 ++cnt; 35 int j; 36 do 37 { 38 j=st[top--]; 39 belong[j]=cnt; 40 size[cnt]++; 41 ins[j]=0; 42 } 43 while (j!=x); 44 } 45 } 46 void spfa(int dis[N]) 47 { 48 memset(dis,0,sizeof(dis)); 49 memset(can,0,sizeof(can)); 50 int t=belong[1]; 51 dis[t]=size[t]; 52 can[t]=1; 53 queue
             
               p; 54 p.push(t); 55 while (!p.empty()) 56 { 57 int now=p.front(); 58 p.pop(); 59 for (int i=point[now]; i; i=Next[i]) 60 if (dis[v[i]]

C送外卖

时间限制 : - MS 空间限制 : 365536 KB

评测说明 : 时限1000ms

问题描述

暑期期间，何老板闲来无事，于是买了辆摩托车，签约某团外卖，跑起来送外卖的业务。

何老板负责的区域里有n个住宅小区(编号1到n)，小区间通过m条双向道路相连，两个小区间最多只有一条道路相连，也不存在某小区自己到它自己的道路。每条道路有一定的长度。

何老板先到1号小区的餐馆去领餐，然后去k个小区送餐(编号2,3,4,...,k+1)，最终到n号小区的加油站去给摩托车加油。要到k个小区去送餐，根据下单时间，公司规定了其中某些小区送餐的先后顺序，比如i小区的餐必须在给j小区送餐前送到。何老板希望在满足公司要求的情况下，使得行走的总路程最少，请你帮他计算一下。

例如，下图所示，起点为1号终点为8号小区。期间要给2、3、4、5号小区送餐。公司规定，给2号小区送餐后才能给3号小区送餐，给3号小区送餐后才能给4、5号小区送餐。最短的行程方案是1—>2—>4—>3—>4—>5—>8,总路程为19。

注意，可以先经过某些后送餐的小区而不停下来给它们送餐。假如，要送4号小区后才能给3号小区送餐，何老板可以从2号经过3号到达4号小区，中间虽然经过了3号小区，但他没有停下来，这样就不违法公司的规定了。

输入格式

第一行，3个空格间隔的整数n,m,k

接下来m行，每行三个整数x,y,z表示小区x也小区y间有一条长度为z的道路(1<=x,y<=n 1<=z<=1000)

接下来一行，一个整数t,表示公司有t条要求(0<=t<=k*(k-1)/2)

接下来t行，每行两个整数x和y,表示给x小区送餐后才能给y号小区送餐

(2<=x,y<=k+1 x!=y)

输出格式

一行，一个整数，表示所求最短总路程。

样例输入 1

8 15 4

1 2 3

1 3 4

1 4 4

1 6 2

1 7 3

2 3 6

2 4 2

2 5 2

3 4 3

3 6 3

3 8 6

4 5 2

4 8 6

5 7 4

5 8 6

2 3

3 4

3 5

样例输出 1

样例输入 2

8 7 6

1 2 10

2 3 15

3 4 1

4 5 12

5 6 13

6 7 123

7 8 10

7 2

2 6

6 3

3 5

5 4

样例输出 2

588

提示

对于100%的数据 2<=N<=20000, 1<=M<=200000, 0<=K<=20

最短路+状压DP

通过k+1次dijkstra预处理得到dis[i][j]为点i到点j处理出的最短路

f[j][i]表示到达i号点的最小代价，到达i号点时的访问状态为j(j为二进制的状压,记录目前已经访问过的点的集合)

f[s][p]=min{f[j][i]+dis[i][p]}

其中s=j|(1<<p-1) 且 (j&Before[p])==Before[p]

j满足Before[p]的所有前提要求

Before[p]记录到达p号点前应该具备的前提状态

1 #include 
        
           2 #include 
         
            3 #include 
          
             4 #include 
           
              5 #include 
            
               6 using namespace std;  7   8 #define Node pair
             
              //
              <距离，编号>
                9 const int maxk=22; 10 const int INF=1000000000; 11 const int maxm=200005; 12 const int maxn=20005; 13 14 struct Edge 15 { 16 int End, w, Next; 17 Edge(int End=0, int w=0, int Next=0):End(End),w(w),Next(Next){};//构造函数，给End,w,Next赋初值 18 }; 19 20 int n, m, k, All,tot; 21 int Last[maxn],dis[maxk][maxk],f[1048576][maxk],Before[maxk],bin[maxk],d[maxn]; 22 bool Mark[maxn]; 23 Edge e[maxm<<1]; 24 25 int read() 26 { 27 int x=0, f=1;char ch=getchar(); 28 while(ch<'0'||ch>'9'){ if(ch == '-')f=-1;ch=getchar();}; 29 while (ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} 30 return x*f; 31 } 32 33 void add_edge(int u, int v, int w) 34 { 35 e[++tot].End=v, e[tot].w=w, e[tot].Next=Last[u], Last[u]=tot; 36 } 37 38 // 求第(1 ~ k+1)号节点到其余节点的单源最短路 39 void dijkstra(int x) 40 { 41 priority_queue
               
                
                 ,greater
                 
                   >Q; 42 for(int i=1;i<=n;i++) d[i]=INF,Mark[i]=0; 43 d[x]=0; 44 Q.push(make_pair(0,x));//起点进堆(距离,编号) 45 while(!Q.empty()) 46 { 47 int cur=Q.top().second; Q.pop(); 48 if(Mark[cur])continue;else Mark[cur]=1; 49 for(int i=Last[cur];i!=0;i=e[i].Next) 50 { 51 if (d[cur]+e[i].w < d[e[i].End]) 52 { 53 d[e[i].End]=d[cur]+e[i].w; 54 Q.push(make_pair(d[e[i].End], e[i].End)); 55 } 56 } 57 } 58 for(int i=1;i<=k+1;i++)dis[x][i]=d[i]; 59 dis[x][k+2]=d[n]; //为节约空间，dis数组大小为dis[22][22],故用k+2位置来记录x到达n的距离 60 } 61 62 void dp() 63 { 64 int i,j,p,S; 65 for(j=0;j<=All;j++) //枚举节点集合 66 for(i=1;i<=k+1;i++) //枚举i号点，目前到达i号点时的状态为j 67 { 68 if(f[j][i]==-1) continue; //不存在此状态的表示的路径则返回 69 for(p=2;p<=k+1;p++) //枚举从i出发下一个到达的点p 70 { 71 S=(j|bin[p-2]); //将p号节点纳入路径集合 72 if ((j&Before[p])==Before[p]) //判断在p节点送餐前是否已经在题目要求的所有前提节点送餐过 73 if (f[j][i]+dis[i][p]