2020-10-07并查集启发式合并
http://icpc.upc.edu.cn/problem.php?cid=2592&pid=5
题目描述¶
DIDIDI and WNJXYK are good friends. One day, they go to the zoo. The monkeys are playing happily. There are n monkeys named 1-n. At first, the first one hangs its tail on the tree. The other n-1 monkeys, either are caught by other monkeys, or catch other monkeys, or both. In the next m seconds, every second, there will be a monkey releasing its left hand or right hand. And then some monkeys will drop on the floor. Given the relationship between monkeys, calculate the landing time of every monkey.
输入¶
The first line of input contains a positive integer T, telling you there are T test cases followed. Each test case, first line includes two integers n, m. n means number of monkeys, and m as mentioned in the description. Then following n lines, the k-th line has two integers, describe the k-th monkey’s information. The first integer is the index of monkey in its left hand, the second integer is the index of monkey in its right hand. -1 indicates there is nothing in its hand. Then following m lines, the i-th line gives the information at time i-1, every line has two numbers, the first is the index of the monkey, the second is the hand that it releases, 1 is left hand, 2 is right hand. It’s guaranteed that all the monkeys aren’t on the floor at the beginning.
输出¶
For each test case, print a line “Case #x: ”, where x is the case number (starting from 1) and print n integers. The i-th integer is the time monkey i drop in the floor. If monkey i don’t land on the floor, print -1;
样例输入¶
样例输出¶
提示¶
Tips:1≤T≤10,1≤n≤200,000,0≤m≤400,000 Initially, the first monkey’s tail hangs on the tree. The first monkey’s right hand catches the third monkey, the second monkey’s left hand catches the third monkey, and the third’s left hand catches the first monkey while the right hand catches the second. On time 0, the first monkey releases its right hand, no monkey lands on the floor. On time 1, the third monkey releases its left hand, then the second monkey and the third land on the floor.
参考博客¶
https://blog.csdn.net/Cosmic_Tree/article/details/108921892
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int x,y;
};
int ans[200500]={0};
node a[400500]={0};
int vis[200500][3]={0};
int g[200500][2]={0};
int father[200500]={0};
vector<int>deep[200500];
int findfa(int n)
{
if(n==father[n])
return n;
else
return father[n]=findfa(father[n]);
}
int union1(int a,int b)
{
int fa=findfa(a);
int fb=findfa(b);
if(fa==fb)
return 0;
if(deep[fa].size()>deep[fb].size())
swap(fa,fb);
father[fa]=fb;
deep[fb].insert(deep[fb].end(),deep[fa].begin(),deep[fa].end());
}
int union2(int a,int b,int ans1)
{
if(b==-1)
return 0;
int fa=findfa(a);
int fb=findfa(b);
if(fa==fb)
return 0;
int f1=findfa(1);
if(fa==f1)
{
for(int i=0;i<deep[fb].size();i++)
{
ans[deep[fb][i]]=ans1;
}
}
if(fb==f1)
{
for(int i=0;i<deep[fa].size();i++)
{
ans[deep[fa][i]]=ans1;
}
}
if(deep[fa].size()>deep[fb].size())
swap(fa,fb);
father[fa]=fb;
deep[fb].insert(deep[fb].end(),deep[fa].begin(),deep[fa].end());
}
int main()
{
int t;
scanf("%d",&t);
for(int t1=1;t1<=t;t1++)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
father[i]=i;
deep[i].clear();
deep[i].push_back(i);
vis[i][1]=vis[i][2]=0;
ans[i]=-1;
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&g[i][1],&g[i][2]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
vis[a[i].x][a[i].y]=1;
}
for(int i=1;i<=n;i++)
{
if(vis[i][1]==0&&g[i][1]!=-1)
{
union1(i,g[i][1]);
}
if(vis[i][2]==0&&g[i][2]!=-1)
{
union1(i,g[i][2]);
}
}
for(int i=m;i>=1;i--)
{
union2(a[i].x,g[a[i].x][a[i].y],i-1);
}
printf("Case #%d: ",t1);
for(int i=1;i<=n;i++)
{
printf("%d ",ans[i]);
}
printf("\n");
}
return 0;
}
题目描述¶
WNJXYK and DIDIDI are friends. They are thinking about getting strong all the time. They are playing a very hard online game and they can’t defeat any monster in this game now. If they can’t defeat monsters, they will not get EXP and will not get strong forever. They finally found that the only way for them to get strong is to upgrade their equipment with their limited coins. Each equipment can be upgrade many times with paying some money. And of course, they will get power from each upgrade. They have N equipment in total and each equipment can be upgrade for Ki times. At first, equipment are all in Level 0. If you upgrade the ith equipment from Level j-1 to Level j, you will pay Cij coins and get Wij power. They have M coins in total and they want to know the most power they can get with these coins.
输入¶
The first line of input contains a positive integer T telling you there are T test cases followed. In each Test Case, there is two positive integers N,M in the first line indicates that there are N equipment and M coins. The following N Lines, there is a positive integer Ki at first indicates that the ith equipment can be upgrade Ki times. And there are 2Ki positive integers followed Wij,Cij.
输出¶
You need to output one line for each Test Case. “Case #X: Y” means the max power they can get in Xth Test Case is Y.
样例输入¶
1 3 5 1 1 1 2 1 1 5 4 1 5 3
样例输出¶
Case #1: 7
提示¶
Tips:1≤T≤10,1≤N≤20,0≤M≤1e9,0≤Ki≤4,1≤Cij,Wij≤1e9
In this Sample, they can upgrade their equipment like this and this is the only for them to get 7 power with 5 coins.
解析¶
双向DFS+二分优化
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1e18;
struct node
{
ll x,y;
};
ll sum1[100][100]= {0};
ll p1[100][100]= {0};
ll n,m;
node ans[5005000]= {0};
ll max1=-INF;
ll cnt=0;
ll size1[100]= {0};
bool cmp(node a,node b)
{
return a.y<b.y;
}
ll dfs1(ll k,ll e,ll sum,ll p)
{
if(k>e)
{
ans[++cnt]=node{sum,p};
max1=max(max1,sum);
return 0;
}
for(ll i=0; i<=size1[k]; i++)
{
if(p+p1[k][i]>m)
continue;
dfs1(k+1,e,sum+sum1[k][i],p+p1[k][i]);
}
dfs1(k+1,e,sum,p);
}
ll find1(ll num)
{
ll l=1,r=cnt+1;
while(l<r)
{
ll mid=(l+r)/2;
if(ans[mid].y<num)
l=mid+1;
else if(ans[mid].y>num)
r=mid;
else if(ans[mid].y==num)
l=mid+1;
}
if(ans[l-1].y<=num)
return l-1;
else
return -1;
}
ll dfs2(ll k,ll e,ll sum,ll p)
{
if(k>e)
{
ll pos=find1(m-p);
if(~pos)
max1=max(max1,sum+ans[pos].x);
max1=max(max1,sum);
return 0;
}
for(int i=0; i<=size1[k]; i++)
{
if(p+p1[k][i]>m)
continue;
dfs2(k+1,e,sum+sum1[k][i],p+p1[k][i]);
}
dfs2(k+1,e,sum,p);
}
int main()
{
int t;
scanf("%d",&t);
for(int t1=1; t1<=t; t1++)
{
scanf("%lld%lld",&n,&m);
cnt=0;
for(ll i=1; i<=n; i++)
{
scanf("%lld",&size1[i]);
for(ll j=1; j<=size1[i]; j++)
{
ll x,y;
scanf("%lld%lld",&sum1[i][j],&p1[i][j]);
sum1[i][j]+=sum1[i][j-1];
p1[i][j]+=p1[i][j-1];
}
}
max1=-INF;
dfs1(1,n/2,0,0);
sort(ans+1,ans+1+cnt,cmp);
ans[0].x=-INF;
for(ll i=1; i<=cnt; i++)
{
ans[i].x=max(ans[i-1].x,ans[i].x);
}
dfs2(n/2+1,n,0,0);
printf("Case #%d: %lld\n",t1,max1);
}
return 0;
}