C++博客-逸娴阁

lca rmq

iyixiang — Thu, 13 Aug 2009 01:55:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include 2#include 3#include阅读全文

iyixiang 2009-08-13 09:55 发表评论

lca tarjan / RMQ

iyixiang — Thu, 13 Aug 2009 01:46:00 GMT

摘要: // tarjan Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include 2#include 3#in... 阅读全文

iyixiang 2009-08-13 09:46 发表评论

离线最小值并查集

iyixiang — Sun, 26 Jul 2009 04:45:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include 2#include 3#include阅读全文

iyixiang 2009-07-26 12:45 发表评论

堆箱子

iyixiang — Tue, 21 Jul 2009 13:23:00 GMT

摘要: #include#includeusing namespace std;class union_find{public: union_find(int n=30000); ~union_find();&... 阅读全文

iyixiang 2009-07-21 21:23 发表评论

wawawawaw

iyixiang — Mon, 20 Jul 2009 13:47:00 GMT

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<queue>
#include<list>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

#define inf 1000000001

struct SNode
{
    int to;
    int price;
    SNode *next;
}forward[1000000+10],Reverse[1000000+10],storage[2000000+10];

int P,Q,allocate;

bool visited[1000000+10];
int dist[1000000+10];

struct cmp{

    bool operator()( int a, int b)
    {
        return dist[a]>dist[b];
    }
};

priority_queue<int,vector<int>,cmp> H;

void initial()
{
    for(int i=0;i<=P;i++)
        Reverse[i].next =forward[i].next =NULL;
    allocate=0;
}

int dijk(SNode graph[])
{
    for(int i=0;i<=P;i++)
        dist[i]=inf;
    memset(visited,false,sizeof(visited));

    visited[1]=true;
    dist[1]=0;
    SNode *p=graph[1].next;
    while(!H.empty() )H.pop ();
    while(p){ printf("%d     ",p->to );H.push(p->to ); dist[p->to]=p->price;p =p->next;}
    int cnt=0;
    while(!H.empty ()){printf("%d ",H.top ());H.pop ();}
    while(!H.empty ()){
        int k=0;
        do{
            if(H.empty ())break;
            if(k)H.pop ();
            k=H.top ();printf("%d -----%d--\n",k,++cnt);

        }while(visited[k] );
        if(H.empty () )break;
        H.pop ();
        printf("asdfsdf\n");
        visited[k]=true;

        // relax

        p=graph[k].next;
        while(p){printf("-%d- ",p->to );
            if( !visited[p->to ] &&  dist[k]+p->price< dist[p->to] ){

                dist[p->to ]= dist[k]+p->price;
                H.push (p->to );
            }
            p=p->next;
        }
    }
    int ret=0;
    for(int i=1;i<=P;i++){
        ret+=dist[i];
    }
    return ret;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&P,&Q);
        initial();
        int sor,des,price;
        for(int i=0;i<Q;i++){
            scanf("%d %d %d",&sor,&des,&price);
            // push
            SNode *p=&storage[allocate++];
            p->to=des;
            p->price=price;
            p->next =forward[sor].next;
            forward[ sor].next =p;

            SNode *q=&storage[allocate++];
            q->to =sor;
            q->price=price;
            q->next =Reverse[des].next;
            Reverse[des].next=q;
        }
        int ans=dijk(forward);
    ans+=dijk(Reverse);
        printf("%d\n",ans);
    }
    return 0;
}

iyixiang 2009-07-20 21:47 发表评论

dfs 割点（邻接表和矩阵）

iyixiang — Mon, 20 Jul 2009 11:21:00 GMT

iyixiang 2009-07-20 19:21 发表评论

cantor 康托

iyixiang — Mon, 20 Jul 2009 04:56:00 GMT

1
2void cantor(int N,int K)
3{ // N! Kth
4    // cantor extend
5    int x=K,cant[100],n=2;
6    memset(cant,0,sizeof(cant));
7    for( ; x ; n++){
8        printf("%d*%d! ",x%n,n-1);
9        cant[n]=x%n;
10        x/=n;
11    }
12    // convert to permutation
13    int p[100];memset(p,0,sizeof(p));
14    for(int i=n-1;i>=1;i--){
15        // cant []
16        int cnt=0;
17        for(int  j=2;j<=n;j++){
18            // p[]
19            if(cnt==cant[i] && !p[j]){
20                p[j]=i;
21                break;
22            }
23            if( p[j]<i)cnt++;
24        }
25    }
26    //out
27    for(int i=n;i>=2;i--){
28        printf("%d ",p[i]);
29    }
30    while(n<=N){printf("%d ",n++);}
31    printf("\n");
32}
33

iyixiang 2009-07-20 12:56 发表评论

Cow Exhibition

iyixiang — Wed, 15 Jul 2009 13:59:00 GMT

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<queue>
#include<algorithm>
using namespace std;

#define offset 100010

struct SNode
{
    int si,fi;
}node[110];

int dp[300000+10];
bool  flag[300000+10];

bool cmp(const SNode a,const SNode b)
{
    return a.si <b.si ;
}

int main()
{
    int N;
    while(scanf("%d",&N)!=EOF){
        for(int i=0;i<N;i++){
            scanf("%d %d",&node[i].si,&node[i].fi);
    //        node[i].fi +=offset;
            node[i].si +=offset;
        }
        sort(node,node+N,cmp);
        memset(dp,0,300000*sizeof(int));
        memset(flag,false,sizeof(flag));
        int up=0,k=0;
        for(k=0;k<N && node[k].si<=offset;k++){
            int si=node[k].si ,fi=node[k].fi;
            if( fi<=0)continue;
            for(int j=1;j<=up;j++){
                if(flag[j]){
                            printf("-------%d %d--------\n",si-offset,fi);
                    int n=j+si-offset;
                    if( fi+dp[j]>0 || !flag[n] )
                        dp[n]+=fi+dp[j];
                    flag[n]=true;
                    up=max(n,up);
                }
            }
            if( fi>0 || !flag[si] )
                dp[si]+=fi;
            flag[si]=true;
            up=max(si,up);
        }

        for( ;k<N;k++){
            int si=node[k].si,fi=node[k].fi ;
            if(si-offset+fi<=0)continue;
            printf("-------%d %d--------\n",si-offset,fi);
            for(int j=up;j>0;j--){
                if(flag[j]){
                    int n=j+si-offset;
                    if(fi+dp[j]>0 || !flag[n] )
                        dp[n]+=fi+dp[j];
                    printf("%d  -->  %d    %d \n",j-offset,n-offset,dp[n]);
                    flag[n]=true;
                    up=max(n,up);
                }
            }
            if( fi>0 || !flag[si])
                dp[si]+=fi;
            flag[si]=true;
            up=max(si,up);
        }
        int ans=0;
        for(int i=offset;i<=up;i++){
            if(dp[i]>=0 && flag[i]){
                printf("%d %d\n",i-offset,dp[i]);
                ans=max(ans,i-offset+dp[i]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

iyixiang 2009-07-15 21:59 发表评论

wa

iyixiang — Tue, 14 Jul 2009 13:05:00 GMT

iyixiang 2009-07-14 21:05 发表评论

knight

iyixiang — Sun, 12 Jul 2009 02:02:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include 2#include 3#include阅读全文

iyixiang 2009-07-12 10:02 发表评论

C++博客-逸娴阁

lca rmq

lca tarjan / RMQ

离线最小值 并查集

堆箱子

wawawawaw

dfs 割点 （邻接表和矩阵）

cantor 康托

Cow Exhibition

wa

knight

离线最小值并查集

dfs 割点（邻接表和矩阵）