帶權最大團數量模板

typedef long long ll;
typedef pair<ll, ll> pll;
struct BKB{
    static const int MAX_N = 50;
    typedef bitset<MAX_N> bst;
    bst N[MAX_N];
    int n;
    ll wei[MAX_N], ans, cc;
    BKB(int _n = 0): n(_n), ans(0), cc(0){
        for(int i = 0; i < _n; ++ i)
            N[i].reset();
    }
    void add_edge(int a, int b) {
        N[a][b] = N[b][a] = 1;
    }
    void set_wei(int a, ll w) {
        wei[a] = w;
    }
    ll CNT(bst P) {
        //if vertices have no weight
        //return P.count();
        ll rt = 0;
        for(int i = P._Find_first(); i < n; i = P._Find_next(i) ) 
            rt += wei[i];
        return rt;
    } 
    void pro(bst P, ll cnt = 0) {
        if (!P.any()){
            if(cnt == ans)
                ++ cc;
            else if(cnt > ans) {
                ans = cnt;
                cc = 1;
            }
            return;
        }
        // "<" can be change to "<=" if we don't need to count
        if ( CNT(P) + cnt < ans) 
            return;
        int u = P._Find_first();
        bst now = P & ~N[u];
        for (int i = now._Find_first(); i < n; i = now._Find_next(i) ) {
            pro(P & N[i], cnt + wei[i]);
            P[i] = 0;
        }
        return;
    }
    pll solve() {
        bst tmp;
        tmp.reset();
        for(int i = 0; i < n; ++ i)
            tmp[i] = 1;
        pro(tmp);
        return pll(ans, cc);
    }
} ss(0);

1978 . 邀請函 (最大團)

　　這是一題最大團（最大獨立集就是補圖的最大團），而我使用常見的手法，Bron–Kerbosch algorithm。
雖說Bron–Kerbosch algorithm可以用來計算最大團。
但是實際上它是一個列舉極大團(maximal clique)的演算法，
如果我們不需要所有極大團，我們就可以對這個算法做一個優化。

以下講解是對於已經會Bron–Kerbosch algorithm的人，要是不會請先學會ＸＤ。


  BronKerbosch1(R, P, X):
       if P and X are both empty:
           report R as a maximal clique
       for each vertex v in P:
           BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
           P := P \ {v}
           X := X ⋃ {v}
這是維基百科的Bron–Kerbosch algorithm虛擬碼，我們可以看到，Ｘ集合唯一的作用，就是判斷這是不是極大團。
所以我們發現，如果要算最大團，Ｘ根本沒用嘛，所以直接整個殺掉，

變成以下這樣。

  BronKerbosch1(R, P):
       if P is empty:
           report R as a clique
       for each vertex v in P:
           BronKerbosch1(R ⋃ {v}, P ⋂ N(v))
           P := P \ {v}
對，其實我只是把Ｘ刪掉而已，就這樣。

如果有機會我再補Bron–Kerbosch algorithm。
//待補

-------------------------------------------
然後是說這題還要解決二分圖的case，
藉由某定理（？），可以知道，當二分圖時。

最大點獨立＋最大邊獨立（匹配）＝Ｖ

所以只要求最大匹配就好，輕輕鬆。
同樣如果有機會我再補可以算二分圖最大匹配的增廣路算法說明。
//待補


最後，
1.由於我比較笨，時限內跑不完，所以利用時間剪枝（快要超過時間就卡掉）。
2.將degree由小到大排會跑比較快唷。

以下直接附code

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int MAX_N = 80;
typedef bitset<MAX_N> bst;
typedef pair<int,int> pii;
bst N[MAX_N],empty;
int n,m,ans;
void BKB(bst R,bst P) {
 if (P==empty){
  ans=max(ans,(int)R.count());
  return;
 }
 if ((R|P).count()<=ans) return;
 if (double(clock())/CLOCKS_PER_SEC > 0.199) return;
 int u=P._Find_first();
 bst now=P&~N[u];
 for (int i=now._Find_first();i<n;i=now._Find_next(i)) {
  R[i]=1;
  BKB(R,P&N[i]);
  R[i]=0;
  P[i]=0;
 }
 return;
}
vector<pii> v;
bool bi(){
 if(n/2%2) return 0;
 for(pii ii:v)
  if(ii.F>=n/2||ii.S<n/2) return 0;
 return 1;
}
int ym[80];
bitset<80> arv;
bool DFS(int x){
 for(int i=n/2;i<n;i++)
  if(N[x][i]&&!arv[i]){
   arv[i]=1;
   if(ym[i]==-1||DFS(ym[i])){
    ym[i]=x;
    return 1;
   }
  }
 return 0;
}
int match(){
 memset(ym,-1,sizeof ym);
 int cnt=0;
 for(int i=0;i<n/2;i++){
  arv.reset();
  if(DFS(i))
   cnt++;
 }
 return cnt;
}
int deg[MAX_N];
int rev[MAX_N];
int main(){
 srand(time(0));
 ios_base::sync_with_stdio(0); cin.tie(0);
 cin>>n>>m;
 bst x; x.reset();
 int tmp[n];
 for(int i=0;i<n;++i){
  x[i]=1;
  tmp[i]=i;
  N[i].set();
  N[i][i]=0; 
 }
 while(m--){
  int a,b; cin>>a>>b;
  if(a>b) swap(a,b);
  v.emplace_back(a,b);
  deg[a]++;
  deg[b]++;
 }
 if(bi()){
  for(int i=0;i<n;i++)
   N[i].reset();
  for(pii ii:v)
   N[ii.F][ii.S]=N[ii.S][ii.F]=1;
  cout<<n-match()<< '\n';
  return 0;
 }
 
 sort(tmp,tmp+n, [&](const int &a, const int &b) { return deg[a] < deg[b]; });
 for(int i=0;i<n;i++){
  rev[tmp[i]]=i;
 }
 for(pii ii:v){
  ii.F=rev[ii.F]; ii.S=rev[ii.S];
  N[ii.F][ii.S]=N[ii.S][ii.F]=0;
 }
 BKB(empty,x);
 cout<<ans<< '\n';
}

TIOJ 1967 千湖之路4

　　先說想法，再說作法，最後說證明。

想法：

　　既然要配N對，然後每對又要相鄰，感覺好難QQ，

　　但是題目都說有N*(N+1)個人了，感覺好像很多，

　　所以就試試看，把所有人分成Ｎ段，然後每段取一對？！

　　所以現在總共N段，每段N+1人。

作法：

　　由於取的一對兩兩數值大小要相鄰，那不如從小的配對開始取，

　　我們對人，從左到右編號0~N*(N+1)-1，接下來，按照每個人的大陸人指數排序，

　　我們從大陸人指數小的人開始看，

　　假設現在他編號是X，他處在第B段(    B=X/(N+1)    )，

　　我們看看第B段有沒有人，

　　要是沒有人，我們說現在X佔據第B段（第B段的人是X），

　　那如果有人呢？

　　那太好了，我們可以把當下佔據B的人和X湊成一對。

　　然後把所有剛剛所有被占據的區段清空。

　　然後封鎖B區段，讓以後所有人再也進不來。

　　最後，既然有N段，那麼自然會湊成N對。

證明：

　　每次我們想要找到新的一對時，都是看看該區段有沒有人，

　　按照鴿籠原理，既然我們只有N段，那麼當我看完N人若是沒有配對，

　　那N個人肯定是一人占據一段，

　　所以第N+1人不管屬於哪段，都會有人跟他配對（好幸福），

　　所以我們知道，每N+1人，至少能湊出一對，

　　而剛好總人數就是N*(N+1)可以湊出N對

以下附code

#include <bits/stdc++.h>
using namespace std;
#define SZ(x) x.size()
#define IOS do{ios_base::sync_with_stdio(0); cin.tie(0);}while(0)
const int INF=1e9+7;
const int MAX=1000;
int arr[MAX*(MAX+1)],box[MAX*(MAX+1)],las[MAX],ans[MAX*2],p,n;
bitset<MAX> used;
bool cmp(int a,int b){
 return arr[a]<arr[b];
}
int main(){
 IOS;
 cin>>n;
 int nn=n*(n+1);
 for(int i=0;i<nn;i++){
  cin>>arr[i];
  box[i]=i;
 }
 memset(las,-1,n*4);
 used.reset();
 sort(box,box+nn,cmp);
 stack<int> st; while(SZ(st)) st.pop();
 for(int i=0;i<nn;i++){
  int x=box[i],b=x/(n+1);
  if(used[b]) continue;
  if(las[b]==-1){
   las[b]=x;
   st.push(b);
  }
  else{
   ans[p++]=las[b];
   ans[p++]=x;
   used[b]=1;
   while(SZ(st)) las[st.top()]=-1,st.pop();
  }
 }
 sort(ans,ans+p);
 for(int i=0;i<p;++i){
  if(i) cout<< ' ';
  cout<<ans[i];
 }
 cout<< '\n';
 return 0;
}

TNFSHOJ 328 I'm Diene!

　　這題其實在考數學，跟甚麼化學根本沒關係，大家應該很很容易看出來。

其實用簡單的說法就是，把重邊去掉之後，把每個連通塊分別壓平，然後看各看有幾個面。

最後輸出面數量*10。

但是甚麼甚麼是面

題目中給了很大的提示，就是正六面體只有五個面。

因為壓平就會變五個。

所以簡單來說，對於所有輸入，要直接將它壓平，以計算有幾個面，

那麼對於一個平面上的圖，可由歐拉公式得知對於每個連通塊

F-E+V=1

F是面數

E是邊數$$
{\displaystyle F-E+V-C=1}

V是頂點數

所以要求的面數就是F=E-V+1

所以就用用並查集 去掉重邊之後算算就行，以下附程式碼。

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) (x).size()

const int MAX=123456;

set<int> st[MAX];

int f[MAX],ans[MAX];

int que(int x){

    if(f[x]==x)    return x;

    return f[x]=que(f[x]);

}

void uni(int x,int y){

    f[que(x)]=que(y);

}

int main(){

    int n,m;

    cin>>n>>m;

    for(int i=0;i<n;i++)    f[i]=i;

    while(m--){

        int x,y;

        cin>>x>>y;

        if(x==y)    continue;

        if(x>y)    swap(x,y);

        st[x].insert(y);

        uni(x,y);

    }   

    for(int i=0;i<n;i++){

        if(i==que(i))    ans[i]++;

        ans[que(i)]+=SZ(st[i])-1;

    }

    int ma=0;

    for(int i=0;i<n;i++)

        ma=max(ma,ans[i]);

    cout<<ma*10<< '\n';

    return 0;

}

TIOJ 1726 Dice Wars

  老實說 我這題真的AC得很莫名其妙
本來一點想法也沒有 然後用一些詭異的優化答案就出來了?!

先不管複雜度 說說中心思想

先開n個vector
然後若是第i個位置是k
那麼在第 k 個vector丟入i

若詢問為a,b

那麼就是將所有a所在的位置
都詢問離該點最近的 b 的位置(在b的vector做lower_bound)

所以這樣每步就會是 O( SZ(vec[a]) lg( SZ(vec[b]) ) )
很明顯若是 SZ(vec[a])>SZ(vec[b])
我們可以交換a,b 達到較好的複雜度

最後
有兩個小小技巧
1.
把所有已經回答的詢問存起來
要是以前已經問過 就可以直接回答
2.
如果有連續三個以上一樣的數字
中間的可以全部都不要存

然後我就不會算複雜度了
但是有一種構造方法可以弄成O(n*sqrt(n)*lg(n) )
就是共sqrt(n)個數字 每個數字有sqrt(n)個
詢問種類最多約 sqrt(n)*sqrt(n)/2
每個次詢問是sqrt(n) lg(n)
所以是O(sqrt(n)*sqrt(n)/2*sqrt(n)*lg(n))=O(n*sqrt(n)*lg(n) )

如果有神人會證複雜度務必告訴我

2018/3/8 補證明
我們已經知道每次詢問複雜度是O( SZ(vec[a]) lg( SZ(vec[b]) ) )
假設SZ(vec[a])<=SZ(vec[b])
考量下列兩種情形

1 . SZ(vec[a])<=sqrt(n)
　這時每次詢問都是O( sqrt(n) lg( n ) )
　總詢問q次　所以此部分詢問複雜度是O( q sqrt(n) lg( n ) )

2 . sqrt(n)<=SZ(vec[a])<=SZ(vec[b])
　我們知道大小大於sqrt(n)的vec，最多只有sqrt(n)個
　也就是說，要在此情形詢問vec[a]，最多只會問sqrt(n)次
　也就是說，對於vec[a]裡面每一個元素，最多只會問sqrt(n)次
　而總元素數量是n，所以總複雜度就是O( n sqrt(n) lg( n ) )

所以此題的複雜度就是O( (n+q) sqrt(n) lg( n ) )

#include <bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef priority_queue<pll,vector<pll>,greater<pll> > heap;
typedef vector<int>::iterator iter;
//macro
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REP1(i,a,b) for(ll i=(a);i<=(b);i++)
#define mkp make_pair
#define pb push_back
const int INF=1e9;
const ll MA=1e6+5;
const ll MOD=1e9+7;
//}}}
int n,m;
vector<int> v[60010];
map<pii,int> mp;
int arr[60010];
int main(){
 ios_base::sync_with_stdio(0); cin.tie(0);
 cin>>n>>m;
 int k;
 for(int i=1;i<=n;i++)
  cin>>arr[i];
 for(int i=1;i<=n;i++){
  if(arr[i-1]!=arr[i]||arr[i+1]!=arr[i])
   v[arr[i]].emplace_back(i);
 }
 int a,b;
 while(m--){
  cin>>a>>b;
  if(!SZ(v[a])||!SZ(v[b])){
   cout<<"-1\n";
   continue;
  }
  if(a==b){
   cout<<"0\n";
   continue;
  }
  if(a>b) swap(a,b);
  if(mp.find({a,b})!=mp.end()){
   cout<<mp.find({a,b})->second<< '\n';
   continue;
  }
  if(SZ(v[a])>SZ(v[b])) swap(a,b);
  int mi=INF;
  for(int i=0,si=SZ(v[a]);i<si;i++){
   int x=lower_bound(ALL(v[b]),v[a][i])-v[b].begin();
   if(x!=SZ(v[b])) mi=min(mi,v[b][x]-v[a][i]);
   if(x){
    x--;
    mi=min(mi,v[a][i]-v[b][x]);
   }
  }
  cout<<mi<< '\n';
  if(a>b) swap(a,b);
  mp[{a,b}]=mi;
 }
 return 0;
}