2020-08-08
http://icpc.upc.edu.cn/problem.php?id=14431
题目¶
14431: 线段
题目描述¶
平面上有N个不相交的线段，编号1到N，需要模拟下落，即线段不旋转地垂直向下移动到X轴下面。如下图：
现在要你来模拟这个过程，每次向下移动一个线段，N次后移走全部线段。但有一个要求：移动一个线段时不能和其他线段相碰。因此选择线段的次序很重要。请输出你制定的次序方案，方案可能有多个，你只要输出其中的一个。
输入¶
第一行包含 1 个整数 N，1≤N≤5000。 下面 N 行，每行 4 个整数 X1,Y1,X2,Y2，0 ≤ X1,Y1,X2,Y2 ≤ 10000。表示第 1 号到第 N 号线段的 2 个 端点。
输出¶
一行 N 个整数，是 1 到 N 的一个排列，表示按次序先后下落的线段编号。
样例输入¶
【样例1】 4 1 3 2 2 1 1 3 2 2 4 7 3 3 3 5 3
【样例2】 4 0 0 1 1 1 2 0 3 2 2 3 3 4 0 3 1
【样例3】 3 4 6 5 5 2 1 15 1 3 2 8 7
样例输出¶
【样例1】 2 4 1 3 【样例2】 4 3 1 2 【样例3】 2 3 1
拓扑排序，枚举并判断两两之间的次序，然后再跑一遍拓扑排序即可。
/**
*
* ━━━━━━━━━神兽出没━━━━━━━━━
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████ ┃+
* ┃ ┃ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃
* ┃ ┃ + + + +
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ + 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃ +
* ┃ ┗━━━┓ + +
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*
* ━━━━━━━━━感觉萌萌哒━━━━━━━━━
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x1,x2,y1,y2;
};
node a[5050]= {0};
vector<int>w[5050];
int in[5050]= {0};
int pd(int x,int y)
{
int min1=max(a[x].x1,a[y].x1),max1=min(a[x].x2,a[y].x2);
if(min1>max1)
return 0;
double kx=(a[x].y1-a[x].y2)*1.0/(a[x].x1-a[x].x2);
if(a[x].x1==a[x].x2)
kx=0;
double ky=(a[y].y1-a[y].y2)*1.0/(a[y].x1-a[y].x2);
if(a[y].x1==a[y].x2)
ky=0;
double x1=a[x].y1+kx*1.0*(min1-a[x].x1);
double x2=a[x].y1+kx*1.0*(max1-a[x].x1);
double y1=a[y].y1+ky*1.0*(min1-a[y].x1);
double y2=a[y].y1+ky*1.0*(max1-a[y].x1);
if(min(x1,x2)>min(y1,y2)||max(x1,x2)>max(y1,y2))
return 1;
else
return 0;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
if(a[i].x1>a[i].x2)
{
swap(a[i].x1,a[i].x2);
swap(a[i].y1,a[i].y2);
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(i==j)
continue;
if(pd(i,j))
{
w[j].push_back(i);
in[i]++;
}
}
}
priority_queue<int,vector<int>,less<int> >w1;
queue<int>ans;
for(int i=1; i<=n; i++)
{
if(in[i]==0)
w1.push(i);
}
while(!w1.empty())
{
int x=w1.top();
w1.pop();
ans.push(x);
for(int i=0; i<w[x].size(); i++)
{
in[w[x][i]]--;
if(in[w[x][i]]==0)
{
w1.push(w[x][i]);
}
}
}
while(!ans.empty())
{
printf("%d ",ans.front());
ans.pop();
}
return 0;
}
题目¶
14850: 奖金
题目描述¶
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。 于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。
输入¶
第一行两个整数n,m，表示员工总数和代表数； 以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。
输出¶
若无法找到合法方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。
样例输入¶
样例输出¶
提示¶
80％的数据满足n<=1000，m<=2000； 100％的数据满足n<=10000，m<=20000。
拓扑排序
/**
*
* ━━━━━━━━━神兽出没━━━━━━━━━
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████ ┃+
* ┃ ┃ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃
* ┃ ┃ + + + +
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ + 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃ +
* ┃ ┗━━━┓ + +
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*
* ━━━━━━━━━感觉萌萌哒━━━━━━━━━
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>w[105050];
int in[105050]= {0};
int ans[100500]={0};
struct node
{
int x,y;
};
int main()
{
int n,m,a,b;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
scanf("%d%d",&a,&b);
w[b].push_back(a);
in[a]++;
}
queue<node>w1;
for(int i=1; i<=n; i++)
{
if(in[i]==0)
w1.push(node{i,100}),ans[i]=100;
}
ll sum=0;
while(!w1.empty())
{
node p=w1.front();
w1.pop();
for(int i=0; i<w[p.x].size(); i++)
{
in[w[p.x][i]]--;
ans[w[p.x][i]]=max(ans[w[p.x][i]],p.y+1);
if(in[w[p.x][i]]==0)
{
w1.push(node{w[p.x][i],ans[w[p.x][i]]});
}
}
}
for(int i=1;i<=n;i++)
{
if(in[i]!=0) ///判环
{
printf("Poor Xed\n");
return 0;
}
sum+=ans[i];
}
printf("%lld\n",sum);
return 0;
}