【并查集】利用并查集优化可用时间（POJ1456 Supermarket）
给你n个商品，每个商品有销售利润和保质期，问如何安排利润最大。
并查集模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int a[N];
int parent(int x)
{
if(x==a[x])return x;
a[x]=parent(a[x]);
return a[x];
}
void merg(int x,int y)
{
x=parent(x);
y=parent(y);
a[x]=y;
}
void init()
{
for(int i=1;i<N;i++)a[i]=i;
}
|
本题思路
首先根据价格由高到低，其次保质期由低到高排序。
并查集初始化为每一天都可用的状态，先安排利润高的商品，安排最后一天再销售。若这一天不可用，用并查集找到下一个可用天数；若并查集父节点为0，代表没有可用天数，放弃安排这个商品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
using namespace std;
const int N = 1e5;
void solve();
void init();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
int a[N];
int parent(int x)
{
if(x==a[x])return x;
a[x]=parent(a[x]);
return a[x];
}
void merg(int x,int y)
{
x=parent(x);
y=parent(y);
a[x]=y;
}
bool cmp(const pii&a,const pii&b)
{
return a.first>b.first||(a.first==b.first&&a.second<b.second);
}
void solve()
{
int n;
while(cin>>n)
{
for(int i=1;i<=10000;i++)a[i]=i;
vecpi h(n);
for(int i=0;i<n;i++)cin>>h[i].first>>h[i].second;
sort(h.begin(),h.end(),cmp);
int ans=0;
for(int i=0;i<n;i++)
{
int t=parent(h[i].second);
if(t)
{
ans+=h[i].first;
merg(t,t-1);
}
}
cout<<ans<<endl;
}
}
void init()
{
}
|
