NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » xavier13540 的個人資料 » 顯示文章
 文章

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

文章 - xavier13540

頁: [1]
1
NPSC2005高中組決賽 / Re: NPSC 2005 高中組 決賽 H.光輪2005
« 於: 四月 04, 2018, 01:36:18 am »
構造一張圖 G = (V, E),其中
  • V 裡的任一元素代表兩人的所在位置,以無序對 (i, j) (若 hi = hj),或有序對 (i, j+1/2) (若 min{hj, hj+1} < hi < max{hj, hj+1}) 表示。
  • 設 u, v ∈ V。規定 uv ∈ E 若且唯若兩人可以在只上山或下山一次的情況下從 u 到達 v。
不難發現題目要問的就是從 (0, n+1) 到任意 (i, i) 的最短路徑長度減 1,可用一次 BFS 解決。因為 |V| = O(n2),且每個頂點的度數 (degree) 都不超過 4,可知整體的時間複雜度是 O(n2)。
值得一提的是,一定存在一條從 (0, n+1) 到某個 (i, i) 的路徑。我們把 G 裡的頂點分成下面這幾種,並討論它們的度數。
  • (0, 0), (0, n+1), (n+1, n+1) 的度數都是 1。
  • 若 i ≠ 0, n+1 且 hi = 0,則 (0, i) 和 (i, n+1) 的度數都是 2。
  • 若 i ≠ 0, n+1,則 (i, i) 的度數是 3。
  • 若 i ≠ j 且 hi = hj,則 (i, j) 的度數是 4 (若 i, j 同為山頂或山谷) 或 0 (若 i, j 一者是山頂另一者是山谷)。
  • 設 v := (i, j+1/2) 為一合法頂點,則 v 的度數是 2。
令 H 為 G 中包含頂點 (0, n+1) 的連通部分 (connected component)。因為 H 的頂點度數和為偶數,可知 H 必定包含某個 (i, i),亦即存在從 (0, n+1) 到某個 (i, i) 的路徑。

以下是我的 C++ code:
代碼: [選擇]
#include<cassert>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

#define N 210
typedef pair<int, int> pii;
int n, h[2*N];
vector<int> g[4*N*N];
bool vis[4*N*N];
int state(int i, int j){
    if(i > j){
        swap(i, j);
    }
    return i*(2*n+3)+j;
}
int move(int i, int j, int di, int dj){
    int c = (i&2)-1;
    if(j&1){
        if(c*h[i+2*di] < c*h[j+dj]){
            return state(i+di, j+dj);
        }else if(c*h[i+2*di] == c*h[j+dj]){
            return state(i+2*di, j+dj);
        }else{
            return state(i+2*di, j);
        }
    }else{
        if(c*h[i+2*di] < c*h[j+2*dj]){
            return state(i+di, j+2*dj);
        }else if(c*h[i+2*di] == c*h[j+2*dj]){
            return state(i+2*di, j+2*dj);
        }else{
            return state(i+2*di, j+dj);
        }
    }
}
bool meet(int v){
    return v/(2*n+3) == v%(2*n+3);
}

int main(){
    while(scanf("%d", &n), n){
        h[0] = h[2*n+2] = 0;
        for(int i=1; i<=n; i++){
            scanf("%*d%d", h+2*i);
        }
        scanf("%*d");
        for(int i=0; i<(2*n+3)*(2*n+3); i++){
            g[i].clear();
        }
        g[state(0, 0)].push_back(move(0, 0, 1, 1));
        g[state(0, 2*n+2)].push_back(move(0, 2*n+2, 1, -1));
        g[state(2*n+2, 2*n+2)].push_back(move(2*n+2, 2*n+2, -1, -1));
        for(int j=4; j<=2*n-2; j+=4) if(h[j] == 0){
            g[state(0, j)].push_back(move(0, j, 1, -1));
            g[state(0, j)].push_back(move(0, j, 1, 1));
            g[state(j, 2*n+2)].push_back(move(j, 2*n+2, -1, -1));
            g[state(j, 2*n+2)].push_back(move(j, 2*n+2, 1, -1));
        }
        for(int i=2, c=1; i<=2*n; i+=2, c*=(-1)){
            for(int j=i; j<=2*n; j+=4) if(h[i] == h[j]){
                g[state(i, j)].push_back(move(i, j, -1, -1));
                g[state(i, j)].push_back(move(i, j, -1, 1));
                g[state(i, j)].push_back(move(i, j, 1, -1));
                g[state(i, j)].push_back(move(i, j, 1, 1));
            }
            for(int j=1; j<=2*n-1; j+=4) if(h[j-1]<h[i] && h[i]<h[j+1]){
                g[state(i, j)].push_back(move(i, j, -1, -c));
                g[state(i, j)].push_back(move(i, j, 1, -c));
            }
            for(int j=3; j<=2*n+1; j+=4) if(h[j-1]>h[i] && h[i]>h[j+1]){
                g[state(i, j)].push_back(move(i, j, -1, c));
                g[state(i, j)].push_back(move(i, j, 1, c));
            }
        }
        bool sol = false;
        memset(vis, false, sizeof(vis));
        queue<pii> bfs;
        bfs.push(make_pair(0, state(0, 2*n+2)));
        vis[state(0, 2*n+2)] = true;
        while(!bfs.empty()){
            pii p = bfs.front(); bfs.pop();
            int d=p.first, v=p.second;
            if(meet(v)){
                printf("%d\n", d-1);
                sol=true; break;
            }
            for(int i=0; i<(int)g[v].size(); i++) if(!vis[g[v][i]]){
                bfs.push(make_pair(d+1, g[v][i]));
                vis[g[v][i]] = true;
            }
        }
        assert(sol);
    }
    return 0;
}


2
NPSC2013高中組初賽 / Re: pC.胖胖天大大薯
« 於: 三月 09, 2014, 09:39:03 pm »
好set 不用嗎
基本上就是
1. 把數列由小到大
2. 如果這個數沒在set裡 加進去
    如果這個數的兩倍沒在set裡 也加進去
    否則當天就只好不吃薯條了
代碼: [選擇]
#include<stdio.h>
#include<algorithm>
#include<set>
#define N 100010
using namespace std;
int a[N];
set<int>s;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",a+i);
        sort(a+1,a+n+1);
        s.clear();
        for(int i=1;i<=n;i++){
            if(s.find(a[i])==s.end())s.insert(a[i]);
            else if(s.find(a[i]<<1)==s.end())s.insert(a[i]<<1);
        }
        printf("%d\n",s.size());
    }
    return 0;
}

3
NPSC2012高中組初賽 / Re: pB. 老蚯的寶物
« 於: 十一月 26, 2012, 06:20:47 pm »
這題用 STL 的 string + stack 程式碼可以寫得超短。

4
NPSC2012高中組初賽 / Re: pD. 長長的蚯蚓天天長長
« 於: 十一月 26, 2012, 06:15:19 pm »
雖然這樣的做法時間複雜度為 O(N*M2),
但可以先用快速冪的技巧算出 A 的 N 次方,
http://www.csie.ntnu.edu.tw/~u91029/DivideAndConquer.html#a4
這樣時間複雜度則會降為 O(lgN*M2),
就算再乘上 T 也會過了。
請問一下為什麼時間複雜度是 O(lgN*M2) 呢?矩陣乘法時間複雜度不是 O(M3) 嗎?

5
NPSC2012高中組初賽 / pC. 好多星星
« 於: 十一月 26, 2012, 01:16:53 pm »
先對百科全書中的星座點集合 P 做以下處理:
1. 將所有的點座標減掉 P0(即將圖形平移使 P0 位於原點)
2. 設 θ = Arg(P1),將圖形旋轉 -θ,即新座標 (x', y') 滿足
┌ x '┐  ┌ cosθ  sinθ ┐┌ x ┐
│    │=│                ││    │
└ y' ┘  └ -sinθ cosθ ┘└ y ┘
3. 設 r=|P0P1|,將圖形縮小成 1/r 倍;這樣,就可以使 P0 在 (0, 0) 而 P1 在 (1, 0)
4. 對所有點對 x 座標做排序,若 x 座標相同,對 y 座標做排序
接著,對星空中的星座,枚舉兩個點,透過上述的座標變換方式,將一點變換到 (0, 0),另一點變換到 (1, 0),並同樣對點座標排序,檢查是否有一個星空中的星座可以變換成百科全書上的星座。
有 n 個百科全書上的星座要檢查,枚舉 m 的星空中的星座,枚舉 w(w-1) 個變換方式,排序時間複雜度 O(wlog w),所以總時間複雜度 O(nmw3log w)
說個感想,我原本輸出答案後面有多一個空格收到 WA,抱著不太可能過的心情把空格去掉,在結束前兩分鐘上傳居然收到了 YES(有點失望?)
以下是我寫的爛爛的 code
代碼: [選擇]
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define N 90
#define V 20
#define EPS 1e-8
using namespace std;
struct point{
    double x,y;
    bool operator!=(point another){
        return fabs(another.x-x)>EPS||fabs(another.y-y)>EPS;
    }
}p[N][V],q[N][V],temp[V];
int v[N],w[N];
bool found[N];
bool cmp(point a,point b){
    if(fabs(a.x-b.x)<EPS)return a.y<b.y;
    return a.x<b.x;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        bool sad=1;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",v+i);
            for(int j=0;j<v[i];j++)scanf("%lf%lf",&p[i][j].x,&p[i][j].y);
            for(int j=1;j<v[i];j++){
                p[i][j].x-=p[i][0].x;
                p[i][j].y-=p[i][0].y;
            }
            p[i][0].x=p[i][0].y=0;
            double dx=p[i][1].x,dy=p[i][1].y;
            double r=hypot(dx,dy);
            double COS=dx/r,SIN=dy/r;
            for(int j=0;j<v[i];j++){
                double x=p[i][j].x,y=p[i][j].y;
                p[i][j].x=(x*COS+y*SIN)/r;
                p[i][j].y=(-x*SIN+y*COS)/r;
            }
            sort(p[i],p[i]+v[i],cmp);
        }
        memset(found,0,sizeof(found));
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",w+i);
            for(int j=0;j<w[i];j++)scanf("%lf%lf",&q[i][j].x,&q[i][j].y);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)if(v[i]==w[j]){
                bool found2=0;
                for(int k=0;k<w[j];k++){
                    bool found3=0;
                    for(int l=0;l<w[j];l++)if(k!=l){
                        for(int i2=0;i2<w[j];i2++){
                            temp[i2].x=q[j][i2].x-q[j][k].x;
                            temp[i2].y=q[j][i2].y-q[j][k].y;
                        }
                        bool found4=1;
                        double dx=q[j][l].x-q[j][k].x,dy=q[j][l].y-q[j][k].y;
                        double r=hypot(dx,dy);
                        double COS=dx/r,SIN=dy/r;
                        for(int i2=0;i2<w[j];i2++){
                            double x=temp[i2].x,y=temp[i2].y;
                            temp[i2].x=(COS*x+SIN*y)/r;
                            temp[i2].y=(-SIN*x+COS*y)/r;
                        }
                        sort(temp,temp+w[j],cmp);
                        for(int i2=0;i2<w[j];i2++)if(p[i][i2]!=temp[i2]){
                            found4=0;break;
                        }
                        if(found4){
                            found3=1;break;
                        }
                    }
                    if(found3){
                        found2=1;break;
                    }
                }
                if(found2){
                    found[i]=1;break;
                }
            }
        }
        for(int i=0;i<n;i++)if(found[i]){
            if(sad){
                printf("%d",i+1);
                sad=0;
            }
            else printf(" %d",i+1);
        }
        if(sad)puts("so sad");
        else putchar('\n');
    }
    return 0;
}


6
NPSC2009高中組決賽 / NPSC 2009 高中組決賽 F. 飛機上有蛇
« 於: 十一月 10, 2012, 01:43:08 pm »
構造一個最小費用最大流模型,將每個空格視作節點,並對於每個節點 i 拆成兩個節點 i 和 i'。設源點為 s 且匯點為 t,構造這些邊:
1. s->i, 其中容量為 2, 費用為 0
2. i'->t, 其中容量為 2, 費用為 0
3. 若 i 與節點 j 相鄰則構造 i->j', 其中容量為 1, 費用為 0
4. 若 i 位於邊界(牆壁)則構造 i->i', 其中容量為 1, 費用為 1
一個迴路(貪食蛇)在模型中有順逆時針兩種,而一個邊界到邊界的路徑(不貪食蛇)在模型中亦有兩種方向。設模型中的最小費用為 mc,最大流為 mf,原圖空格數為 sp,則有
Case 1: mf<2*sp,表示空格無法被填滿
Case 2: mf=2*sp,此時邊界到邊界的路徑數即為 mc/2
此外,若 sp=0,要輸出 -1。
我最小費用最大流是用 spfa 實作,時間複雜度為 O(n3m3),在 ZJ 上跑了 4.7 秒。
代碼: [選擇]
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define N 25
#define INF 1000000000
using namespace std;
struct edge{int to,flow,cap,cost,rev;};
char map[N][N];
int d[2*N*N],a[2*N*N],s,t,mc,mf;
vector<edge>G[2*N*N];
queue<int>spfa;
bool inspfa[2*N*N];
pair<int,int>p[2*N*N];
void push_edge(int from,int to,int cap,int cost){
    edge e;
    e.to=to,e.flow=0,e.cap=cap,e.cost=cost,e.rev=G[to].size();
    G[from].push_back(e);
    e.to=from,e.cap=0,e.cost=-cost,e.rev=G[from].size()-1;
    G[to].push_back(e);
}
void mcmf(){
    mc=mf=0;
    while(1){
        for(int i=0;i<=t;i++)d[i]=INF;
        d[s]=0;
        a[s]=INF;
        spfa.push(s);
        while(!spfa.empty()){
            int i=spfa.front();
            spfa.pop();
            inspfa[i]=0;
            for(int j=0;j<G[i].size();j++){
                int to=G[i][j].to;
                if(G[i][j].cap>G[i][j].flow&&d[to]>d[i]+G[i][j].cost){
                    d[to]=d[i]+G[i][j].cost;
                    a[to]=min(a[i],G[i][j].cap-G[i][j].flow);
                    p[to]=make_pair(i,j);
                    if(!inspfa[to]){
                        spfa.push(to);
                        inspfa[to]=1;
                    }
                }
            }
        }
        if(d[t]==INF)return;
        for(int i=t;i!=s;i=p[i].first){
            int rev=G[p[i].first][p[i].second].rev;
            G[p[i].first][p[i].second].flow+=a[t];
            G[i][rev].flow-=a[t];
        }
        mc+=d[t]*a[t];
        mf+=a[t];
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,sp=0,ans;
        scanf("%d%d",&n,&m);
        s=0,t=2*n*m+1;
        for(int i=s;i<=t;i++)G[i].clear();
        for(int i=0;i<n;i++)scanf("%s",map[i]);
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(map[i][j]=='.'){
            push_edge(s,i*m+j+1,2,0);
            push_edge(n*m+i*m+j+1,t,2,0);
            if(i+1<n&&map[i+1][j]=='.'){
                push_edge(i*m+j+1,n*m+(i+1)*m+j+1,1,0);
                push_edge((i+1)*m+j+1,n*m+i*m+j+1,1,0);
            }
            if(j+1<m&&map[i][j+1]=='.'){
                push_edge(i*m+j+1,n*m+i*m+j+2,1,0);
                push_edge(i*m+j+2,n*m+i*m+j+1,1,0);
            }
            if(!i||i+1==n||!j||j+1==m)push_edge(i*m+j+1,n*m+i*m+j+1,1,1);
            sp++;
        }
        mcmf();
        if(!sp||mf<2*sp)ans=-1;
        else ans=mc/2;
        printf("%d\n",ans);
    }
    return 0;
}


7
NPSC2009高中組初賽 / Re: NPSC 2009 高中組 初賽 D.賽車
« 於: 十月 02, 2012, 08:45:09 pm »
我這題是用 DP 解的 設 dp[ i][j][k][l] = 在第 i 行時三部車的所在位置為 j, k, l ( j < k < l ) 的最小油耗
若第 (0, j), (0, k), (0, l) 格皆非障礙物 則 dp[0][j][k][l] = 3 否則為 INF
接著對於三部車子在第 i 行時的所有可能位置 (i, j), (i, k), (i, l) 枚舉所有可能的換車方式 利用 dp[i-1] 算出在該狀態下到達終點的最小油耗
時間複雜度 O(R3C) 對於 R ≦ 10, C ≦ 50 的數據大小而言可以輕鬆解決 我的程式在 ZJ 上的執行時間為 8 ms
以下是我恐怖的程式碼 ( 換車方式太多種了 )
代碼: [選擇]
#include<stdio.h>
#include<algorithm>
#define R 10
#define C 50
#define INF 1000000000
using namespace std;
char map[R][C+1];
int dp[C][R][R][R];
int main(){
    int T,r,c,start[3],start_size;
    scanf("%d",&T);
    while(T--){
        start_size=0;
        scanf("%d%d",&r,&c);
        for(int i=0;i<r;i++){
            scanf("%s",map[i]);
            if(map[i][c-1]=='C')start[start_size++]=i;
        }
        for(int i=0;i<r;i++)for(int j=i+1;j<r;j++)for(int k=j+1;k<r;k++){
            if(map[i][0]!='#'&&map[j][0]!='#'&&map[k][0]!='#')dp[0][i][j][k]=3;
            else dp[0][i][j][k]=INF;
        }
        for(int i=1;i<c;i++)for(int j=0;j<r;j++)for(int k=j+1;k<r;k++)for(int l=k+1;l<r;l++){
            dp[i][j][k][l]=INF;
            if(map[j][i]!='#'&&map[k][i]!='#'&&map[l][i]!='#'){
                if(j>0){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l-1]+6);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k-1][l+1]+6);
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k][l+1]+5);
                    if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l-1]+6);
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j-1][k+1][l+1]+6);
                }
                if(k-j>1){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l+1]+5);
                }
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l-1]+4);
                dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l]+3);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l+1]+4);
                if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l-1]+5);
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l]+4);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k+1][l+1]+5);
                if(k-j>2){
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l-1]+6);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l]+5);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k-1][l+1]+6);
                }
                if(k-j>1){
                    if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l-1]+5);
                    dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l]+4);
                    if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k][l+1]+5);
                }
                if(l-k>2)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l-1]+6);
                if(l-k>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l]+5);
                if(r-l>1)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j+1][k+1][l+1]+6);
            }
        }
        if(dp[c-1][start[0]][start[1]][start[2]]<INF)printf("%d\n",dp[c-1][start[0]][start[1]][start[2]]);
        else puts("Impossible");
    }
    return 0;
}

8
想法:
考慮一個圖 G0,若處理事件 i 後能處理事件 j,節點 i 和節點 j 就用有向邊連接。題目要求的就是找圖上盡量少的路徑,使得所有點都被涵蓋。

做法:
構造一個二分圖 G,把在 G0 的節點 v 拆成 v 和 v'。若在 G0 中,節點 u 和節點 v 之間存在有向邊,則連接二分圖中的 u 和 v'。題目所求即為 (G0 節點數) - (G 的最大配對數)。
求二分圖的最大配對可用 maximum flow 解決,我的程式碼使用 Ford-Fulkerson Algorithm,時間複雜度 O(m3),在 ZJ 上跑了 2 秒。

代碼: [選擇]
//我習慣測資數用 T,所以事件數就用 n 了
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define N 1010
using namespace std;
struct accident{
    int t,x,y;
}acc[N];
struct edge{
    int to,rev;
    bool cap;
};
int n;
bool visited[2*N];
pair<int,int>p[2*N];
vector<edge>G[2*N];
bool cmp(accident a,accident b){
    return a.t<b.t;
}
void push_edge(int from,int to){
    edge e;
    e.to=to,e.rev=G[to].size(),e.cap=1;
    G[from].push_back(e);
    e.to=from,e.rev=G[from].size()-1,e.cap=0;
    G[to].push_back(e);
}
bool dfs(int i){
    visited[i]=1;
    if(i==2*n+1){
        for(int j=i;j;j=p[j].first){
            int rev=G[p[j].first][p[j].second].rev;
            G[p[j].first][p[j].second].cap=0;
            G[j][rev].cap=1;
        }
        return 1;
    }
    for(int j=0;j<G[i].size();j++)if(!visited[G[i][j].to]&&G[i][j].cap){
        p[G[i][j].to]=make_pair(i,j);
        if(dfs(G[i][j].to))return 1;
    }
    return 0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int mf=0;//最大配對或最大流量
        scanf("%d",&n);
        for(int i=0;i<2*n+2;i++)G[i].clear();
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&acc[i].t,&acc[i].x,&acc[i].y);
            push_edge(0,i+1);
            push_edge(n+i+1,2*n+1);
        }
        sort(acc,acc+n,cmp);
        for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
            if(abs(acc[j].x-acc[i].x)+abs(acc[j].y-acc[i].y)<=acc[j].t-acc[i].t)push_edge(i+1,n+j+1);
        }
//Ford-Fulkerson Algorithm
        while(1){
            memset(visited,0,2*n+2);
            if(dfs(0))mf++;
            else break;
        }
        printf("%d\n",n-mf);
    }
    return 0;
}


頁: [1]