absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-12] 266E
[破碎的状态] [-9] 546E

[破碎的状态] [-11] USACO 1.3 Wormholes

absi2011 posted @ Jul 11, 2016 11:31:07 AM in 刷题记录 with tags 拓扑排序 usaco 小高考 , 584 阅读

题意在这里:

http://www.nocow.cn/index.php/Translate:USACO/wormhole

实际上我只是练一发拓扑排序..

/*
    ID: absi2011
    PROG: wormhole
    LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int next[25];
int x[25],y[25];
int ans=0;
int visit[25];
int n;
int in[25];
void topo_sort()
{
    int i;
    int m=n*2;
    for (i=0;i<m;i++)
    {
        in[i]=0;
    }
    for (i=0;i<m;i++)
    {
        if (next[i]!=-2) in[next[i]]++;
    }
    static int que[105];
    int front=0,rail=0;
    for (i=0;i<m;i++)
    {
        if (in[i]==0)
        {
            que[rail++]=i;
        }
    }
    for (;front<rail;front++)
    {
        int t=que[front];
        if (next[t]==-2) continue;
        in[next[t]]--;
        if (in[next[t]]==0)
        {
            que[rail++]=next[t];
        }
    }
    if (rail!=m) ans++;
}
void dfs(int x)
{
    if (x>=n)
    {
        topo_sort();
        return;
    }
    if (visit[x])
    {
        dfs(x+1);
        return;
    }
    int i;
    visit[x]=true;
    for (i=x+1;i<n;i++)
    {
        if (visit[i]) continue;
        next[i*2]=x*2+1;
        next[x*2]=i*2+1;
        visit[i]=true;
        dfs(x+1);
        visit[i]=false;
    }
    visit[x]=false;
}
int main()
{
    freopen("wormhole.in","r",stdin);
    freopen("wormhole.out","w",stdout);
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    for (i=0;i<n;i++)
    {
        int j;
        int t=-1;
        for (j=0;j<n;j++)
        {
            if (y[i]==y[j])
            {
                if (x[j]<=x[i]) continue;
                if ((t==-1)||(x[j]<=x[t]))
                {
                    t=j;
                }
            }
        }
        next[i*2+1]=t*2;
    }
    dfs(0);
    printf("%d\n",ans);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter