【Henu ACM Round#16 D】Bear and Two Paths

在这里输入题意

【题解】

先搞一条a到b的路径
a c x3 x4 x5....xn-2 d b
然后第二个人的路径可以这样
c a x3 x4 x5...xn-2 b d
也即加两条边[a,x3] [xn-2,b]
所以最少只需要n+1条边。
(尽量让边共用,只有两条边是需要特殊加进去的
(可以这样理解,加一条边的话,无论怎么加都不够的。所以加两条肯定是最优的了。
这样贪就好了

但是n=4的时候；‘

会发现两对起点和终点中肯定有一对是有一条边**直接相连((的(在路径存在的情况下)

所以始终无解

【代码】

#include <bits/stdc++.h>

using namespace std;

int n,k,a,b,c,d;

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> k;

    cin >>a>>b>>c>>d;

    if (n==4){

        cout<<"-1"<<endl;

    }else{

        int m = n+1;

        if (k<m){

            cout<<"-1"<<endl;

        }else{

            cout<<a<<" "<<c;

            int first =-1;

            for (int i = 1;i <= n;i++)

                if (i!=a && i!=b && i!=c && i!=d)

                    cout<<" "<<i;

            cout <<" "<<d<<" "<<b<<endl;

            cout<<c<<" "<<a;

            for (int i = 1;i <= n;i++)

                if (i!=a && i!=b && i!=c && i!=d)

                    cout<<" "<<i;

            cout<<" "<<b<<" "<<d<<endl;

        }

    }

	return 0;

}

巴特西

【Henu ACM Round#16 D】Bear and Two Paths

最新文章

热门文章