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 阅读(176) |
评论 (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 阅读(226) |
评论 (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 阅读(387) |
评论 (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 阅读(209) |
评论 (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 阅读(243) |
评论 (0) |
编辑 收藏
1
2void dfs(int k,int father,int deep)
3{
4 //printf("%d ",k);
5 c[k]=1;
6 Ancestor[k]=deep;
7 dep[k]=deep;
8 int tot=0;
9 for(int i=1;i<=N;i++){
10 if( graph[k][i] && i!=father && c[i]==1){
11 Ancestor[k]=min(Ancestor[k],dep[i]);
12 }
13 if( graph[k][i] && c[i]==0){
14 dfs(i,k,deep+1);
15 Ancestor[k]=min(Ancestor[k],Ancestor[i]);
16
17 if( (k==Root && ++tot>=2)
18 || ( k!=Root && Ancestor[i]>=dep[k]) )
19 Cut[k]=1;
20 }
21 }
22
23 c[k]=2;
24}
1#define MAXN 100
2struct SNode
3{
4 int to;
5 SNode *next;
6}node[MAXN];
7int N;
8int Root;
9int c[MAXN];
10int Ancestor[MAXN];
11int dep[MAXN];
12int Cut[MAXN];
13int graph[MAXN];
14void dfs(int k,int father,int deep)
15{
16 c[k]=1;
17 dep[k]=deep;
18 Ancestor[k]=deep;
19 int tot=0;
20 SNode *p=node[k].next ;
21 while(p){
22 int v=p->to ;p=p->next;
23 if( c[v]==1&& v!=father )
24 Ancestor[k]=min(Ancestor[k],dep[v]);
25 if(c[v]==0){
26 dfs(v,k,deep+1);
27 Ancestor[k]=min(Ancestor[k],Ancestor[v]);
28 if( (k==Root && ++tot>=2 )
29 || (k!=Root && Ancestor[v]>=dep[k]) )
30 Cut[k]=1;
31 }
32 }
33 c[k]=2;
34}
35posted @
2009-07-20 19:21 iyixiang 阅读(244) |
评论 (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 阅读(230) |
评论 (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<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;
}
posted @
2009-07-15 21:59 iyixiang 阅读(364) |
评论 (0) |
编辑 收藏
2009年7月14日
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<queue>
#include<algorithm>
using namespace std;
int N,a[5000+10],cnt[5000+10],len[5000+10];
int main()
{
while(scanf("%d",&N)!=EOF){
for(int i=0;i<N;i++)
scanf("%d",&a[i]);
memset(cnt,0,sizeof(cnt));
memset(len,0,sizeof(len));
int ans=0;
for(int i=0;i<N;i++){
cnt[i]=len[i]=1;
for(int j=i-1;j>=0;j--){
if( a[j]<a[i])continue;
if(a[j]==a[i] ){
if( len[j]==len[i] ){
if(len[i]!=1)
cnt[j]+=cnt[i];
len[i]=1;
cnt[i]=0;
}
else if(len[j]>len[i]){
cnt[j]=0;
}
break;
}
else {
if( len[j]+1>len[i]){
len[i]=len[j]+1;
cnt[i]=cnt[j];
}
else if( len[j]+1==len[i])
cnt[i]+=cnt[j];
}
}
ans=max(ans,len[i]);
}
int num=0;
for(int i=0;i<N;i++){
printf("%d %d %d \n",a[i],len[i],cnt[i]);
if(len[i]==ans)
num+=cnt[i];
}
printf("%d %d\n",ans,num);
}
return 0;
}
posted @
2009-07-14 21:05 iyixiang 阅读(118) |
评论 (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 阅读(168) |
评论 (0) |
编辑 收藏