Coding Beans: Graph

顯示具有 Graph 標籤的文章。顯示所有文章

2016年4月12日星期二

[TIOJ 1896][IOI 2014] Game

原題連結

這道題目的思維還是有點難度的，但是code寫起來非常精簡，官方提供的構造解法甚至hasEdge裡只須要寫1行......有興趣的可以到IOI2014網站去膜拜一下。

2016年3月11日星期五

[Wunder Fund Round 2016 pD][DP] Hamiltonian Spanning Tree

link
You can view official tutorial here.
Here I will explain some points I consider important when trying to solve the problem.
There may be some mistakes in grammar due to my poor English QAQ.
Any correction of algorithm or grammar is welcomed.

It's not hard to find that x>y and x<y are two different problem: One is to use more tree edges as possible while the other is to use less tree edges.

2016年3月4日星期五

[Codeforces Round #286 (Div. 1) pD][Disjoint Set][sqrt method] Mr. Kitayuta's Colorful Graph

原題連結
這題我提供兩個解法和兩份code，都具有相當的啟發性。

[COCI Contest #7 pE][Disjoint Set] KUGLICE

可以在這邊的Contest 7中找到題目說明和測資

2016年3月3日星期四

[Codeforces Good Bye 2014 pB][Disjoint Set] New Year Permutation

原題連結
呼呼，這是並查集專題中的一題，題目本身並不難。
先對題目和並查集的聯繫做一點說明。

[Codeforces Round #218 (Div. 2) pD][Disjoint Set] Vessels

原題連結
一道並查集的頗直覺的題目
難點大概就只有在有沒有想到要用Disjoint Set去做吧......
對於已經滿的vessel i ，執行 fa[i] <- findset(i+1) ，直觀上就是將每個相鄰的滿vessel連接起來，已達到快速查詢可用vessel的效果。

細節上要注意水流到地上的case要做好，不然很容易WA或是TLE。

#include<cstdio>
#define LL long long
using namespace std;
const int maxn=200000+5;
int fa[maxn],cap[maxn],cur[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {fa[i]=i;scanf("%d",cap+i);}
    fa[n]=n;
    scanf("%d",&m);
    for(int i=0,type,a,b;i<m;i++)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%d%d",&a,&b);a--;
            a=findset(a);
            for(;b && a!=n;)
            {
                if(cap[a]-cur[a]>b) cur[a]+=b,b=0;
                else // cap[a]-cur[a]<=b
                {
                    b-=cap[a]-cur[a];
                    cur[a]=cap[a];
                    fa[a]=findset(a+1);
                    a=findset(a);
                }
            }
        }
        else
        {
            scanf("%d",&a);a--;
            printf("%d\n",cur[a]);
        }
    }
}