列表

详情

NC50884. Go on Strike!

描述

There are N cities in Eddy's neverland. There are some flights to connect some pair of cities. Except flight, there's no any other way to shuttle between cities.

However, in some cases, flight attendants may go on strike to fight for their rights. Therefore, some flight may be shut down for a period of time. On the other hand, some flight may come out to compete the market.

In Eddy's neverland, each flight must propose its expected cost to be granted the license to fly. Then, Eddy will choose some flights and grant them the licenses. In order to keep the neverland great, Eddy will choose a minimum total cost flights to grant the license such that each city is possible to connect to each other city by the granted flights.

Since the new coming flight and flight shut down events come everyday, Eddy is not able to find out the best combination of flights with minimum total cost. Please help Eddy to keep his neverland great. Reporting the chosen combination would be too large to check. You only need to tell Eddy what is the most flights needed to connect two cities is under the chosen flights(Not the total cost!).


输入描述

The first line of input contains two space-separated integers N and Q, where N is the number of cities and Q is the number of events.

Following Q lines each contains four space-separated integers . If , there is a new flight coming out between city u_i and city v_i with cost c_i. If , the flight attendants of the flight connecting city u_i and v_i with cost c_i has gone on strike and the flight is shut down.






It's guaranteed that if , the required flight exists.

输出描述

Output Q lines each contains an integer representing the most flights needed to connect two cities in the chosen combination. If there exists two cities which can not be connected through the current flights, output .

It's guaranteed that the chosen combination will be unique.

示例1

输入: 

3 6
1 1 2 1
1 1 3 2
1 2 3 4
1 1 2 8
0 1 2 1
0 2 3 4

输出: 

-1
2
2
2
2
2

示例2

输入: 

4 4
1 1 2 1
1 1 3 2
1 1 4 8
1 2 3 4

输出: 

-1
-1
2
2

说明:

First two flights are not enough to make each pair of cities connected.

First three flights are enough to make each pair of cities connected. The most flights needed to connect some pair of cities results from connecting city 2 and city 3 which needs two flights to connect(so as city 2 and city 4, city 3 and city 4).
The forth flights won't be included in the chosen combination. The scenario remains the same.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 6601ms, 内存消耗: 3328K, 提交时间: 2019-07-23 15:50:43 

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MAXN=10005;
const int MAXM=20005;
const int INF=0x3f3f3f3f;
 
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int _u,int _v,int _w):u(min(_u,_v)),v(max(_u,_v)),w(_w){}
    bool operator < (const Edge &t)const
    {
        return u==t.u ? (v==t.v ? w<t.w : v<t.v) : u<t.u;
    }
}e[MAXM];
 
map<Edge,int>mp;
inline int get_eid(const Edge &u)
{
    if(!mp[u])e[mp[u]=mp.size()]=u;
    return mp[u];
}
 
vector<pair<int,int>> g[MAXN];
bool dfs_add(int u,int f,int p,int &rep)
{
    if(u==p)return 1;
    for(auto &t:g[u])
    {
        int v=t.first,id=t.second;
        if(v==f)continue;
        if(dfs_add(v,u,p,rep))
        {
            if(e[id].w>e[rep].w)
                rep=id;
            return 1;
        }
    }
    return 0;
}
 
int pid[MAXN];
void dfs_del(int u,int f,int id)
{
    pid[u]=id;
    for(auto &t:g[u])
    {
        int v=t.first;
        if(v==f)continue;
        dfs_del(v,u,id);
    }
}
 
ll dp[MAXN];
void dfs_dia(int u,int f,ll &res)
{
    dp[u]=0;
    for(auto &t:g[u])
    {
        int v=t.first;
        if(v==f)continue;
        dfs_dia(v,u,res);
        res=max(res,dp[u]+dp[v]+1);
        dp[u]=max(dp[u],dp[v]+1);
    }
}
 
vector<int> bak;
int main()
{
    int n,q,e_cnt=0;
    scanf("%d%d",&n,&q);
    ll las=0;
    for(int i=1;i<=q;i++)
    {
        int q,u,v,c;
        scanf("%d%d%d%d",&q,&u,&v,&c);
        int eid=get_eid({u,v,c}),keep=0;
        if(q==1)
        {
            int rep=eid;
            if(dfs_add(u,0,v,rep))
            {
                if(rep==eid)
                {
                    bak.push_back(eid);
                    keep=1;
                }
                else
                {
                    g[e[rep].u].erase(find(g[e[rep].u].begin(),g[e[rep].u].end(),make_pair(e[rep].v,rep)));
                    g[e[rep].v].erase(find(g[e[rep].v].begin(),g[e[rep].v].end(),make_pair(e[rep].u,rep)));
                    g[u].push_back({v,eid});
                    g[v].push_back({u,eid});
                }
            }
            else
            {
                g[u].push_back({v,eid});
                g[v].push_back({u,eid});
                e_cnt++;
            }
        }
        else
        {
            auto itr=find(bak.begin(),bak.end(),eid);
            if(itr!=bak.end())
            {
                bak.erase(itr);
                keep=1;
            }
            else
            {
                g[u].erase(find(g[u].begin(),g[u].end(),make_pair(v,eid)));
                g[v].erase(find(g[v].begin(),g[v].end(),make_pair(u,eid)));
                dfs_del(u,0,2*i),dfs_del(v,0,2*i+1),e_cnt--;
                int mi=INF,loc=0;
                for(auto &t:bak)
                    if(pid[e[t].u]>=2*i && (pid[e[t].u]^pid[e[t].v])==1 && e[t].w<mi)
                        mi=e[t].w,loc=t;
                if(loc)
                {
                    g[e[loc].u].push_back({e[loc].v,loc});
                    g[e[loc].v].push_back({e[loc].u,loc});
                    e_cnt++;
                }
            }
        }
        if(!keep)
        {
            if(e_cnt<n-1)printf("%lld\n",las=-1LL);
            else
            {
                ll res=0;
                if(keep)res=las;
                else dfs_dia(1,0,res);
                printf("%lld\n",las=res);
            }
        }
        else printf("%lld\n",las);
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 6341ms, 内存消耗: 3340K, 提交时间: 2019-07-22 00:09:57 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN=10005;
const int MAXM=20005;
const int INF=0x3f3f3f3f;

struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int _u,int _v,int _w):u(min(_u,_v)),v(max(_u,_v)),w(_w){}
    bool operator < (const Edge &t)const
    {
        return u==t.u ? (v==t.v ? w<t.w : v<t.v) : u<t.u;
    }
}e[MAXM];

map<Edge,int>mp;
inline int get_eid(const Edge &u)
{
    if(!mp[u])e[mp[u]=mp.size()]=u;
    return mp[u];
}

vector<pair<int,int>> g[MAXN];
bool dfs_add(int u,int f,int p,int &rep)
{
    if(u==p)return 1;
    for(auto &t:g[u])
    {
        int v=t.first,id=t.second;
        if(v==f)continue;
        if(dfs_add(v,u,p,rep))
        {
            if(e[id].w>e[rep].w)
                rep=id;
            return 1;
        }
    }
    return 0;
}

int pid[MAXN];
void dfs_del(int u,int f,int id)
{
    pid[u]=id;
    for(auto &t:g[u])
    {
        int v=t.first;
        if(v==f)continue;
        dfs_del(v,u,id);
    }
}

ll dp[MAXN];
void dfs_dia(int u,int f,ll &res)
{
    dp[u]=0;
    for(auto &t:g[u])
    {
        int v=t.first;
        if(v==f)continue;
        dfs_dia(v,u,res);
        res=max(res,dp[u]+dp[v]+1);
        dp[u]=max(dp[u],dp[v]+1);
    }
}

vector<int> bak;
int main()
{
    int n,q,e_cnt=0;
    scanf("%d%d",&n,&q);
    ll las=0;
    for(int i=1;i<=q;i++)
    {
        int q,u,v,c;
        scanf("%d%d%d%d",&q,&u,&v,&c);
        int eid=get_eid({u,v,c}),keep=0;
        if(q==1)
        {
            int rep=eid;
            if(dfs_add(u,0,v,rep))
            {
                if(rep==eid)
                {
                    bak.push_back(eid);
                    keep=1;
                }
                else
                {
                    g[e[rep].u].erase(find(g[e[rep].u].begin(),g[e[rep].u].end(),make_pair(e[rep].v,rep)));
                    g[e[rep].v].erase(find(g[e[rep].v].begin(),g[e[rep].v].end(),make_pair(e[rep].u,rep)));
                    g[u].push_back({v,eid});
                    g[v].push_back({u,eid});
                }
            }
            else
            {
                g[u].push_back({v,eid});
                g[v].push_back({u,eid});
                e_cnt++;
            }
        }
        else
        {
            auto itr=find(bak.begin(),bak.end(),eid);
            if(itr!=bak.end())
            {
                bak.erase(itr);
                keep=1;
            }
            else
            {
                g[u].erase(find(g[u].begin(),g[u].end(),make_pair(v,eid)));
                g[v].erase(find(g[v].begin(),g[v].end(),make_pair(u,eid)));
                dfs_del(u,0,2*i),dfs_del(v,0,2*i+1),e_cnt--;
                int mi=INF,loc=0;
                for(auto &t:bak)
                    if(pid[e[t].u]>=2*i && (pid[e[t].u]^pid[e[t].v])==1 && e[t].w<mi)
                        mi=e[t].w,loc=t;
                if(loc)
                {
                    g[e[loc].u].push_back({e[loc].v,loc});
                    g[e[loc].v].push_back({e[loc].u,loc});
                    e_cnt++;
                }
            }
        }
        if(!keep)
        {
            if(e_cnt<n-1)printf("%lld\n",las=-1LL);
            else
            {
                ll res=0;
                if(keep)res=las;
                else dfs_dia(1,0,res);
                printf("%lld\n",las=res);
            }
        }
        else printf("%lld\n",las);
    }
    return 0;
}

上一题

© 2025 nowcoder.com