题目大意:给出一个无向图,要求只保留K条边,并且使尽可能多的点保持原来到点1的最短距离.

题解:先用堆优化的DIJ跑出最短路径树,然后利用bfs,从叶子处开始减边(因为减叶子的边只会影响一个点的最短路径,而从非叶子减边会影响多个点的最短路径)

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 typedef long long ll;  7 struct edge{  8     int v;  9     int id; 10     ll val; 11     int nex; 12 }e[600005]; 13 struct pot{ 14     int v; 15     ll dist; 16     bool operator<(const struct pot & xx)const { 17         return dist>xx.dist; 18     } 19 }; 20 int head[300004]; 21 ll dis[300004]; 22 bool ok[300005]; 23 int pre_e[300004],pre_v[300004]; 24 int n,m,k,cnt; 25 int dev[300004]; 26 void dij(){ 27     priority_queue
          
           pq; 28     struct pot aa; 29     memset(dis,0x7f7f7f7f,sizeof(dis)); 30     dis[1]=0; 31     aa.v=1; 32     aa.dist=0; 33     pq.push(aa); 34     while(!pq.empty()){ 35         struct pot bb=pq.top();pq.pop(); 36         if(dis[bb.v]
           
            dis[bb.v]+e[i].val){ 39 dis[e[i].v]=dis[bb.v]+e[i].val; 40 struct pot cc; 41 cc.v=e[i].v; 42 cc.dist=dis[e[i].v]; 43 pre_v[e[i].v]=bb.v; 44 pre_e[e[i].v]=e[i].id; 45 pq.push(cc); 46 } 47 } 48 } 49 } 50 void build() { 51 for (int i = 2; i <= n; ++i) { 52 int v = pre_v[i]; 53 int id = pre_e[i]; 54 ok[id] = 1; 55 ++dev[v]; 56 } 57 } 58 void bfs(){ 59 if(k>=n-1){ 60 k=n-1; 61 return ; 62 } 63 queue
            
             pp; 64 //k=n-1; 65 int sk=n-1; 66 for(int i=1;i<=n&&sk>k;i++){ 67 if(!dev[i]){ 68 pp.push(i); 69 } 70 } 71 while(sk>k){ 72 int i=pp.front();pp.pop(); 73 dev[pre_v[i]]--; 74 ok[pre_e[i]]=0; 75 sk--; 76 if(dev[pre_v[i]]==0)pp.push(pre_v[i]); 77 } 78 } 79 void adde(int x,int y,ll z,int s){ 80 e[cnt].v=y; 81 e[cnt].val=z; 82 e[cnt].nex=head[x]; 83 e[cnt].id=s; 84 head[x]=cnt++; 85 e[cnt].v=x; 86 e[cnt].val=z; 87 e[cnt].nex=head[y]; 88 e[cnt].id=s; 89 head[y]=cnt++; 90 } 91 int main(){ 92 //freopen("in.txt","r",stdin); 93 scanf("%d%d%d",&n,&m,&k); 94 memset(head,-1,sizeof(head)); 95 for(int i=0;i