首頁 後端開發 php教程 POJ 3107 - Godfather 树型DP..vector慎用..._PHP教程

POJ 3107 - Godfather 树型DP..vector慎用..._PHP教程

Jul 15, 2016 pm 01:21 PM
最佳化 提交 超時

 提交超时..实在觉得没什么好优化的...最多改回至底而上的BFS..但好麻烦,记一堆东西..看discuss才知道主要是vector的原因..改成手写链表..500MS过,,,

 
    选择任意一个点做树的树的root...统计每个点的子树元素个数情况..对于不是root的点..将所有点数N减去当前子树的元素个数num.作为该点的另一个孩子...
 
 
 
 
Program:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<ctime>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 50005
using namespace std;  
struct node
{
      int x,y,next;
}line[MAXN*2];  
int n,AnsNum,AnsData,ans[MAXN],_next[MAXN];
bool used[MAXN];
void addline(int x,int y,int m)
{
      line[m].next=_next[x],_next[x]=m;
      line[m].x=x,line[m].y=y;
      return;
}
int dfs(int x)
{
      int MaxSub=0,num=0,t,k;
      k=_next[x];
      while (k) 
      {
           if (!used[line[k].y])
           {
                 used[line[k].y]=true;
                 t=dfs(line[k].y);
                 MaxSub=max(t,MaxSub);
                 num+=t;
                 used[line[k].y]=false;
           }
           k=line[k].next;
      }
      MaxSub=max(MaxSub,n-(num+1));
      if (MaxSub==AnsData) ans[++AnsNum]=x;
      else 
      if (MaxSub<AnsData)
      { 
             AnsData=MaxSub;
             AnsNum=0,ans[++AnsNum]=x;
      }
      return num+1;
}
int main()
{  
      int i,num; 
      while (~scanf("%d",&n))
      {
              memset(_next,0,sizeof(_next));
              for (i=1;i<n;i++)
              {
                     int x,y;
                     scanf("%d%d",&x,&y);
                     addline(x,y,i*2-1);
                     addline(y,x,i*2); 
              }
              memset(used,false,sizeof(used));
              AnsData=oo; used[1]=true;
              dfs(1);
              sort(ans+1,ans+1+AnsNum);
              printf("%d",ans[1]);
              for (i=2;i<=AnsNum;i++) printf(" %d",ans[i]);
              printf("\n");
      }
      return 0;
}
登入後複製

 


www.bkjia.comtruehttp://www.bkjia.com/PHPjc/477206.htmlTechArticle提交超时..实在觉得没什么好优化的...最多改回至底而上的BFS..但好麻烦,记一堆东西..看discuss才知道主要是vector的原因..改成手写链表..500M...
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1654
14
CakePHP 教程
1413
52
Laravel 教程
1306
25
PHP教程
1252
29
C# 教程
1225
24
WPS Word表格居中應如何操作 WPS Word表格居中應如何操作 Mar 21, 2024 pm 02:21 PM

在使用WPS中的word時常常也需要插入圖片、表格等,但是插入的表格不居中就會影響整個文件的美觀程度,那麼WPS表格居中該怎麼進行設定呢?今天就來教各位小夥伴們是如何進行調整的,具體的操作步驟如下,小夥伴們快來看看! 1.如圖的表格沒有在頁面的中間,不太美觀,想讓其居中。 2.先在表格中點選滑鼠右鍵(如圖)。 3.再點選右鍵選單中的【全選表格】(如圖紅色箭頭處所示)。 4.點選後,該表格就處於被全選的狀態(如下圖所示)。 5.此時點選開啟wps文字的【開始】選項卡(如圖紅色箭頭出所示)。 6、點

美團超時怎麼理賠?美團超時賠付標準! 美團超時怎麼理賠?美團超時賠付標準! Mar 16, 2024 pm 07:55 PM

一、美團超時怎麼賠?美團超時賠付標準!美團超時賠付規則如下:(一)購買了準時寶服務的超時:選擇準時寶服務後,如外賣騎手未能按時送達,系統將自動啟動賠償流程,賠償金額根據訂單細節和超時時長而定。 (二)未購買準時寶的普通超時:1.訂單實際送達時間晚於承諾送達時間10分鐘以​​上、20分鐘以下的,賠付訂單實際支付金額的25%。 2.訂單實際送達時間晚於承諾送達時間20分鐘以上、30分鐘以下的,賠付訂單實際支付金額的30%。 3.訂單實際送達時間晚於承諾送達時間30分鐘以上的,賠付訂單實際支付金額的50%。 4

C++ 程式最佳化:時間複雜度降低技巧 C++ 程式最佳化:時間複雜度降低技巧 Jun 01, 2024 am 11:19 AM

時間複雜度衡量演算法執行時間與輸入規模的關係。降低C++程式時間複雜度的技巧包括:選擇合適的容器(如vector、list)以最佳化資料儲存和管理。利用高效演算法(如快速排序)以減少計算時間。消除多重運算以減少重複計算。利用條件分支以避免不必要的計算。透過使用更快的演算法(如二分搜尋)來優化線性搜尋。

美團跑腿配送超時怎麼辦_美團跑腿配送超時處理方法 美團跑腿配送超時怎麼辦_美團跑腿配送超時處理方法 Mar 28, 2024 am 09:26 AM

1.首先外賣需要了解訂單是由商家自配送還是由美團包配送的,一般而言,商家自配送的接單效率低,常常會出現超時的狀況,可是由於配送方面不由美團參與,所以沒有超時賠付原則。這時您可以看看提交訂單是否有寫明送餐超時的賠償條款,如果有相關條款按照條款索賠就無需多言,商家自會索賠。如果沒有相關規則,建議可以在平台對用餐配送的服務情況進行差評或留言等,或者直接聯繫商家,對配送服務進行投訴,從而協商賠付事宜,實在協商不了的,只能自認倒霉了,下次多加註意吧。 2.超時賠償模式:商家承諾一個送達時間和一個折扣,從用戶

MySQL事務處理:自動提交與手動提交的區別 MySQL事務處理:自動提交與手動提交的區別 Mar 16, 2024 am 11:33 AM

MySQL事務處理:自動提交與手動提交的差異在MySQL資料庫中,事務是一組SQL語句的集合,要麼全部執行成功,要麼全部執行失敗,保證了資料的一致性和完整性。在MySQL中,事務可以分為自動提交和手動提交,其區別在於事務提交的時機以及對事務的控制範圍。以下將詳細介紹自動提交和手動提交的區別,並給出具體的程式碼範例來說明。一、自動提交在MySQL中,如果沒有顯示

深度解讀:為何Laravel速度慢如蝸牛? 深度解讀:為何Laravel速度慢如蝸牛? Mar 07, 2024 am 09:54 AM

Laravel是一款廣受歡迎的PHP開發框架,但有時候被人詬病的就是其速度慢如蝸牛。究竟是什麼原因導致了Laravel的速度不盡人意呢?本文將從多個面向深入解讀Laravel速度慢如蝸牛的原因,並結合具體的程式碼範例,幫助讀者更深入地了解此問題。 1.ORM查詢效能問題在Laravel中,ORM(物件關係映射)是一個非常強大的功能,可以讓

Laravel效能瓶頸揭秘:優化方案大揭秘! Laravel效能瓶頸揭秘:優化方案大揭秘! Mar 07, 2024 pm 01:30 PM

Laravel效能瓶頸揭秘:優化方案大揭秘!隨著網路技術的發展,網站和應用程式的效能優化變得愈發重要。作為一款流行的PHP框架,Laravel在開發過程中可能會面臨效能瓶頸。本文將探討Laravel應用程式可能遇到的效能問題,並提供一些最佳化方案和具體的程式碼範例,讓開發者能夠更好地解決這些問題。一、資料庫查詢最佳化資料庫查詢是Web應用中常見的效能瓶頸之一。在

餓了麼超時了有補償嗎?分享餓了麼超時申請賠償標準! 餓了麼超時了有補償嗎?分享餓了麼超時申請賠償標準! Mar 15, 2024 pm 05:58 PM

一、餓了麼超時了有補償嗎?餓了麼超時了是有補償的,但是前提條件需要用戶購買準時寶或者在購買商品時商家贈送準時寶,有準時寶超時才能有賠付服務哦。餓了麼最新版本類別:便捷生活下載推薦下載:餓了麼最新版本是一款便捷的外帶訂購平台。用戶透過餓了麼app可以輕鬆瀏覽週邊餐廳菜單、下單支付,並享受送餐上門的服務。最新版本的餓了麼也新增了多種特色功能,如拼單、商家優惠等,讓使用者更便宜地享受美食。介面簡潔明了,操作簡單方便,同時支援多種支付方式,帶給使用者更好的使用體驗。二、分享餓了麼超時申請賠償標準! 1

See all articles