今天被傻逼联通坑死了，，目前还没弄懂它坑爹的话费机制
浪费老子10块钱，，我屮艸芔茻
进入正题。。
今天用kruskal写了个题。。大致流程。，其实复杂程度和prim算法差不多。
先按照边排序，然后一个个选出来，用并查集判断是否形成环。
poj2485:
同样，回头整理的时候会给出结题报告的。
直接贴代码；
/*
* =====================================================================================
*
* Filename: 2485.c
*
* Description: poj2485
*
* Version: 1.0
* Created: 2014/7/6 13:55:07
* Revision: none
* Compiler: gcc
*
* Author: ShengRang (), 541628498@qq.com
* Organization:
*
* =====================================================================================
*/
#include <stdio.h>
#define MAXSIZE 600
/* int a[MAXSIZE][MAXSIZE];*/
typedef struct{
int u;
int v;
int c;
}node;
int partition(node a[],int l,int r)
{
int i,j;
i=l;j=r;
node x = a[l];
while(i<j)
{
while(a[j].c >=x.c && i<j)
{
j--;
}
a[i] = a[j];
while(a[i].c <= x.c && i<j)
{
i++;
}
a[j] = a[i];
}
a[i] = x;
return i;
}
void quickSort(node a[],int l,int r)
{
if(l<r)
{
int i;
i = partition(a,l,r);
quickSort(a,l,i-1);
quickSort(a,i+1,r);
}
}
node a[MAXSIZE*MAXSIZE];
int e;
int uset[MAXSIZE];
int find(int x)
{
if(uset[x] != x)
{
uset[x] = find(uset[x]); /* 这句话居然刚开始写错了………… */
}
return uset[x];
}
void makeSet(int n)
{
int i;
for(i=0;i<n;i++)
{
uset[i] = i;
}
return;
}
void addNode(int i,int j,int c)
{
node tmp;
tmp.u = i;
tmp.v = j;
tmp.c = c;
a[e++] = tmp;
}
int kruskal(int n)
{
/* 并查集在这里起了两个作用，
* 判断是否重复的边（因为输入的是邻接矩阵）
* 判断是否形成回路(如果新要加入的边会形成回路，，他们的uset[u],uset[v]会一样)
m用作计算是否已经圈了n-1条边(因为一个树的边是n-1)
*/
int ans=0;
int i;
int m;
int px,py;
for(i=0;i<e;i++)
{
px = find(a[i].u);
py = find(a[i].v);
if(px == py)
continue;
m++;
ans = a[i].c;
uset[py] = px; /* 这句话很重要 */
if(m==n-1)
break;
}
return ans;
}
int main ( int argc, char *argv[] )
{
int T;
scanf("%d",&T);
int n;
int i,j,k;
int x,y;
while(T--)
{
e = 0;
scanf("%d",&n);
makeSet(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&x);
addNode(i,j,x);
}
}
quickSort(a,0,e-1);
/* for(i=0;i<e;i++)
{
printf("u:%d v:%d c:%d \n",a[i].u,a[i].v,a[i].c);
}*/
printf("%d\n",kruskal(n));
}
return 0;
} /* ---------- end of function main ---------- */
然后用poj1182复习了下并查集，注意向量性的关系的使用。
贴代码
/*
* =====================================================================================
*
* Filename: 1182.c
*
* Description: poj1182
*
* Version: 1.0
* Created: 2014/7/5 20:32:25
* Revision: none
* Compiler: gcc
*
* Author: ShengRang (), 541628498@qq.com
* Organization:
*
* =====================================================================================
*/
#include <stdio.h>
#define MAXSIZE 500005
int uset[MAXSIZE];
int dis[MAXSIZE];
void makeSet(int n)
{
int i;
for(i=1;i<=n;i++)
{
uset[i] = i;
dis[i] = 0;
}
return;
}
int find(int x)
{
int tmp = uset[x];
if(x != uset[x])
{
uset[x] = find(uset[x]);
dis[x] = (dis[x] + dis[tmp]) % 3;
}
return uset[x];
}
void unionSet(int x,int y,int px,int py, int rela)
{
uset[px] = py;
dis[px] = (3+rela+dis[y]-dis[x]) % 3;
}
int main ()
{
int n;
int k;
int ans= 0;
int imf;
int x,y;
int px,py;
int rela;
scanf("%d%d",&n,&k);
makeSet(n);
while(k--)
{
scanf("%d%d%d",&imf,&x,&y);
if(imf==2 && x==y)
{
ans++;
continue;
}
else if(x>n || y>n)
{
ans++;
continue;
}
else
{
px = find(x);
py = find(y);
rela = (imf == 1)?0:1;
if(px==py)
{
if(dis[x] != (rela+dis[y])%3)
{
ans++;
}
}
else
{
unionSet(x,y,px,py,rela);
}
}
}
printf("%d\n",ans);
return 0;
} /* ---------- end of function main ---------- */
然后是做了个单调栈的东西。
poj里有三题是单调栈的。今天写了第二个.poj2082。.想写poj2796,未遂
/*
* =====================================================================================
*
* Filename: 2082.c
*
* Description: poj2082
*
* Version: 1.0
* Created: 2014/7/6 15:17:09
* Revision: none
* Compiler: gcc
*
* Author: ShengRang (), 541628498@qq.com
* Organization:
*
* =====================================================================================
*/
#include <stdio.h>
#define MAXSIZE 500010
typedef struct{
int start;
int end;
int val;
}node;
node stack[MAXSIZE];
int top;
void push(node n)
{
top++;
// printf("Top:%d\n",top);
stack[top] = n;
/* printf("Push the node :val:%d,start:%d,end:%d\n",n.val,n.start,n.end);*/
}
node pop()
{
top--;
/* printf("pop the node : val : %d,start %d, end : %d\n",stack[top+1].val,stack[top+1].start,stack[top+1].end);*/
return stack[top+1];
}
void initialise()
{
top = 1;
node tmp;
tmp.start = tmp.end = 0;
tmp.val = 0;
stack[0] = tmp;
return;
}
node GetTop()
{
// printf("top:%d\n",top);
return stack[top];
}
int main ( int argc, char *argv[] )
{
int N;
int i,j,k;
int x;
node tmp;
node t;
int ans;
int curAns;
while(scanf("%d",&N) != EOF, N != -1)
{
ans = 0;
initialise();
x = 0;
tmp.end = tmp.start = 0;
for(i=1;i<=N+1;i++)
{
if(i==N+1)
{
tmp.val = 0;
tmp.start = tmp.end;
}
else
{
scanf("%d%d",&x,&tmp.val);
tmp.start = tmp.end;
tmp.end+=x;
}
/* printf("current node whose VAL is:%d,Start:%d,end:%d\n",tmp.val,tmp.start,tmp.end);*/
/* printf("Top:%d,val:%d,start:%d,end:%d\n",top,GetTop().val,GetTop().start,GetTop().end);*/
while(GetTop().val > tmp.val)
{
// printf("111111~~\n");
t = pop();
curAns = (tmp.start-GetTop().end)*t.val;
/* printf("Current Ans:%d\n",curAns);*/
if(curAns > ans)
ans = curAns;
}
push(tmp);
}
printf("%d\n",ans);
}
return 0;
} /* ---------- end of function main ---------- */
明天要做个最小生成树的报告。今天实在不知道要写点什么。。就这样吧。感觉有点盲目，，不应该这样的。。
明天看看动态规划或者地杰斯特拉，或者把归并和堆排序看了。
然后打算写几个没内容的帖子，，记录一些做掉的题目的poj专题
先这样，晚安