NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2013國中組決賽
 ProblemB-蚯蚓搬家問題

作者 主題: ProblemB-蚯蚓搬家問題  (閱讀 1209 次)

darry140

  • 初級會員
  • **
  • 文章數: 32
    • 檢視個人資料
ProblemB-蚯蚓搬家問題
« 於: 十二月 12, 2013, 07:11:43 pm »

首先要搞懂台大生說的「置換群」是什麼
group_min=置換群裡面最輕的那個
global_min=所有酒裡面最輕的那個
對於每一個置換群
可以發現用group_min來把group裡其他酒換到原位花的錢最少(簡單Greedy)
但是有特例就是你先把global_min跟group_min交換
用global_min把這個group裡面其他酒換回原位
再把global_min跟group_min換回來
----------------
NPSC2013官網公布測資了
官測AC。
----------------
代碼: [選擇]
#include <iostream>
#include <cstring>
#include <cstdio>
#define min(x,y) (x<y?x:y)
#define max_N 100010
#define INF 1e9
using namespace std;
int par[max_N],tar[max_N],wei[max_N],S[max_N],L[max_N],amt[max_N];
bool v[max_N];
void DFS(int src,int idx)
{
int now=src;
S[idx]=0;
L[idx]=INF;
do
{
amt[idx]++;
v[now]=true;
S[idx]+=wei[now];
L[idx]=min(L[idx],wei[now]);
now=tar[now];
}while(now!=src);
}
int main()
{
int T,N,global_L;
cin>>T;
while(T--)
{
cin>>N;
memset(amt,0,sizeof(amt));
memset(v,false,sizeof(v));
global_L=INF;
for(int i=1;i<=N;i++)
scanf("%d",&tar[i]);//IO大
for(int i=1;i<=N;i++)
scanf("%d",&wei[i]),global_L=min(global_L,wei[i]);
int cnt=1;
for(int i=1;i<=N;i++)
if(!v[i])
DFS(i,cnt++);
int ans=0;
for(int i=1;i<cnt;i++)
ans+=min((amt[i]-2)*L[i]+S[i],L[i]+S[i]+(amt[i]+1)*global_L);
cout<<ans<<endl;
}
return 0;
}
« 上次編輯: 十二月 21, 2013, 12:12:06 am 由 darry140 »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2013國中組決賽
 ProblemB-蚯蚓搬家問題