NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組初賽
 NPSC 2005 高中組 初賽 E. 魔法部的任務

作者 主題: NPSC 2005 高中組 初賽 E. 魔法部的任務  (閱讀 1924 次)

xavier13540

  • 新手
  • *
  • 文章數: 7
    • 檢視個人資料
NPSC 2005 高中組 初賽 E. 魔法部的任務
« 於: 八月 28, 2012, 01:47:18 pm »

想法:
考慮一個圖 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;
}

« 上次編輯: 八月 28, 2012, 01:48:51 pm 由 xavier13540 »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組初賽
 NPSC 2005 高中組 初賽 E. 魔法部的任務