codeforce 605B. Lazy Student

题意:n点,m条边。m条边里面标记为1的最小生成树的边,0为非最小生成树的边。给了每条边的权,如果能构成一个最小生成树则输出图,否则-1。

思路:先按权值小,为生成数边的顺序排序。(根据kruskal)再添加每条0边。这里假定(1,3),(2,4)构成环。

 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
const int SIGMA_SIZE = ;
const int MAXNODE = ;
const int MAXS = + ; int n,m;
struct node
{
int u,v,o;
bool operator <(const node &b)const
{
if(u==b.u)
return v>b.v;
return u<b.u;
}
} a[]; int b[];
int c[];
int fun()
{
int e=,x=,y=;
for(int i=;i<=m;i++)
{
if(a[i].v)
{
b[a[i].o]=e;
c[a[i].o]=++e;
}
else
{
if(y>e)
return ;
b[a[i].o]=x;
c[a[i].o]=y;
if(--x==)
{
y+=;
x=y-;
}
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=; i<=m; i++)
{
scanf("%d%d",&a[i].u,&a[i].v);
a[i].o=i;
}
sort(a+,a++m);
if(fun())
{
for(int i=; i<=m; i++)
{
cout<<b[i]<<" "<<c[i]<<endl;
}
}
else
{
cout<<"-1"<<endl;
}
return ;
}
上一篇:605B. Lazy Student(codeforces Round 335)


下一篇:Codeforces Round #335 (Div. 2) D. Lazy Student 贪心+构造