随笔-11  评论-0  文章-0  trackbacks-0
  2009年8月13日
     摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1#include<iostream>  2#include<algorithm>  3#include<cm...  阅读全文
posted @ 2009-08-13 09:55 iyixiang 阅读(161) | 评论 (0)编辑 收藏
     摘要: // tarjan Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1#include<iostream>  2#include<algorithm>  3#in...  阅读全文
posted @ 2009-08-13 09:46 iyixiang 阅读(218) | 评论 (0)编辑 收藏
  2009年7月26日
     摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1#include<iostream>  2#include<algorithm>  3#include<ve...  阅读全文
posted @ 2009-07-26 12:45 iyixiang 阅读(373) | 评论 (0)编辑 收藏
  2009年7月21日
     摘要: #include<iostream>#include<algorithm>using namespace std;class union_find{public:    union_find(int n=30000);    ~union_find();&...  阅读全文
posted @ 2009-07-21 21:23 iyixiang 阅读(197) | 评论 (0)编辑 收藏
  2009年7月20日
#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;
}


            
posted @ 2009-07-20 21:47 iyixiang 阅读(231) | 评论 (0)编辑 收藏

posted @ 2009-07-20 19:21 iyixiang 阅读(231) | 评论 (0)编辑 收藏
 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
posted @ 2009-07-20 12:56 iyixiang 阅读(220) | 评论 (0)编辑 收藏
  2009年7月15日

#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<&& 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;
}





posted @ 2009-07-15 21:59 iyixiang 阅读(347) | 评论 (0)编辑 收藏
  2009年7月14日
wa
posted @ 2009-07-14 21:05 iyixiang 阅读(109) | 评论 (0)编辑 收藏
  2009年7月12日
     摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1#include<iostream>  2#include<cmath>  3#include<queue&...  阅读全文
posted @ 2009-07-12 10:02 iyixiang 阅读(154) | 评论 (0)编辑 收藏
仅列出标题  下一页