ACMクラシックアルゴリズム
<strong>1.n d </strong>
#include<stdio.h>
#include<stdlib.h>
int main(){
int n=3,d=10;
while(1){
scanf("%d%d",&n,&d);
if(n==0&&d==0) break;
long ans=1;
long temp=n;
while(d){
if(d&0x01){
ans*=temp;
}
d>>=1;
temp*=temp;
}
printf("%ld
",ans);
}
return 0;
}
<strong>2. n 2. n </strong>
#include<stdio.h>
#define N 25
int main(){
int T,i,j;
scanf("%d",&T);
long data[N][N];
for(i=1;i<N;i++){data[i][i]=1;data[i][1]=1;}
for(i=2;i<N;i++){
for(j=2;j<i;j++){
data[i][j]=data[i-1][j-1]+j*data[i-1][j];
}
data[i][i]=1;
}
while(T--){
int n;
scanf("%d",&n);
long result=0;
for(i=1;i<=n;i++) result+=data[n][i];
printf("%ld
",result);
}
return 0;
}
<strong>3. quick_mod</strong>
long quick_mod ( long a , long n ,long p ){
long t =a , ret =1;
while( n ){
if( n &1) ret=ret * t-(ret * t/p)*p;
n>>=1; //n ， 2
t = t * t -(t * t/p)*p;
}
return ret ;
}
<strong>4. </strong>
#include<stdio.h>
#define Max 1000000007
void extended_gcd( long a, long b, long &x ,long &y){
if(b==0){ x=1; y=0; return;}
extended_gcd(b,a%b,x,y);
long temp=x;
x=y;
y=temp-a/b*y;
}
long inv(long b , long n){
long x=1,y=2;
extended_gcd(b,n,x,y);
x=(x%n+n)%n;
return x;
}
int main(){
int n,i;
while(scanf("%d",&n)!=EOF){
int m=2*n-1;
long a=1,b=1;
for(i=n;i>0;i--){
a=(a*m)%Max;
m--;
}
for(i=n;i>1;i--){
b=(b*i)%Max;
}
long x=inv(b,Max); //(a/b)%p, (b*x)%p=1
long ans=a*x%Max;
printf("%lld
",ans);
}
return 0;
}
<strong>5. </strong>
#include<stdio.h>
int maxSum(int data[100][100],int n,int m){
int max=-127;
int a,c,i,j,start,all;
for(a=0;a<=n;a++)
for(c=a;c<=n;c++){
start=0;
for(i=a;i<=c;i++) start+=data[i][m];
all=start;
for(i=m-1;i>=0;i--){
if(start<0) start=0;
for(j=a;j<=c;j++) start+=data[j][i];
if(start>all) all=start;
if(all>max) max=all;
}
}
return max;
}
int main(){
int n,i,j;
scanf("%d",&n);
int data[100][100];
if(n>1){
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&data[i][j]);
printf("%d
",maxSum(data,n-1,n-1));
}
else if(n==1){
scanf("%d",&j);
printf("%d
",j);
}
else printf("0
");
return 0;
}
<strong>
6. n </strong>
#include<stdio.h>
#include <stdlib.h>
#define Max 1000000007
int main(){
long t=1;
scanf("%ld",&t);
while(t>0){
long i,a=1,b=2,c=3,n=4;
scanf("%ld%ld%ld%ld",&a,&b,&c,&n);
long sum=a;
if(n==2) sum=b;
else if(n==3) sum=c;
else if(n>3){
n=n-3;
long long ans[9]={1,0,0,0,1,0,0,0,1};
long long temp[9]={1,1,1,1,0,0,0,1,0};
long long p[9];
while(n){
if(n&0x01){
p[0]=(ans[0]*temp[0]+ans[1]*temp[3]+ans[2]*temp[6])%Max;
p[1]=(ans[0]*temp[1]+ans[1]*temp[4]+ans[2]*temp[7])%Max;
p[2]=(ans[0]*temp[2]+ans[1]*temp[5]+ans[2]*temp[8])%Max;
p[3]=(ans[3]*temp[0]+ans[4]*temp[3]+ans[5]*temp[6])%Max;
p[4]=(ans[3]*temp[1]+ans[4]*temp[4]+ans[5]*temp[7])%Max;
p[5]=(ans[3]*temp[2]+ans[4]*temp[5]+ans[5]*temp[8])%Max;
p[6]=(ans[6]*temp[0]+ans[7]*temp[3]+ans[8]*temp[6])%Max;
p[7]=(ans[6]*temp[1]+ans[7]*temp[4]+ans[8]*temp[7])%Max;
p[8]=(ans[6]*temp[2]+ans[7]*temp[5]+ans[8]*temp[8])%Max;
for(i=0;i<9;i++) ans[i]=p[i];
}
n>>=1;
p[0]=(temp[0]*temp[0]+temp[1]*temp[3]+temp[2]*temp[6])%Max;
p[1]=(temp[0]*temp[1]+temp[1]*temp[4]+temp[2]*temp[7])%Max;
p[2]=(temp[0]*temp[2]+temp[1]*temp[5]+temp[2]*temp[8])%Max;
p[3]=(temp[3]*temp[0]+temp[4]*temp[3]+temp[5]*temp[6])%Max;
p[4]=(temp[3]*temp[1]+temp[4]*temp[4]+temp[5]*temp[7])%Max;
p[5]=(temp[3]*temp[2]+temp[4]*temp[5]+temp[5]*temp[8])%Max;
p[6]=(temp[6]*temp[0]+temp[7]*temp[3]+temp[8]*temp[6])%Max;
p[7]=(temp[6]*temp[1]+temp[7]*temp[4]+temp[8]*temp[7])%Max;
p[8]=(temp[6]*temp[2]+temp[7]*temp[5]+temp[8]*temp[8])%Max;
for(i=0;i<9;i++) temp[i]=p[i];
}
sum=(((ans[0]*c)%Max)+((ans[1]*b)%Max)+((ans[2]*a)%Max))%Max;
}
printf("%ld
",sum);
t--;
}
return 0;
}
<strong>
7. </strong>
void quick_sort(int x[],int l,int u){
if(l>=u) return;
int t=x[l];
int i=l;
int j=u+1;
int temp;
while(1){
do{i++;}while(i<=u&&x[i]<t);
do{j--;}while(x[j]>t);
if(i>j)break;
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
temp=x[l];
x[l]=x[j];
x[j]=temp;
quick_sort(x,l,j-1);
quick_sort(x,j+1,u);
}
<strong>
8. fibonacci —— </strong>
#include<stdio.h>
#define M 10000
int main(){
long n=4;
int i,j;
while(scanf("%ld",&n)!=EOF){
int data[2][2]={{1,1},{1,0}};
int sum[2][2]={{1,0},{0,1}};
int temp[2][2];
int result=1;
if(n>2){
n-=2;
while(n){
if(n&1){
temp[0][0]=(sum[0][0]*data[0][0]+sum[0][1]*data[1][0])%M;
temp[0][1]=(sum[0][0]*data[0][1]+sum[0][1]*data[1][1])%M;
temp[1][0]=(sum[1][0]*data[0][0]+sum[1][1]*data[1][0])%M;
temp[1][1]=(sum[1][0]*data[0][1]+sum[1][1]*data[1][1])%M;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
sum[i][j]=temp[i][j];
}
n>>=1;
temp[0][0]=(data[0][0]*data[0][0]+data[0][1]*data[1][0])%M;
temp[0][1]=(data[0][0]*data[0][1]+data[0][1]*data[1][1])%M;
temp[1][0]=(data[1][0]*data[0][0]+data[1][1]*data[1][0])%M;
temp[1][1]=(data[1][0]*data[0][1]+data[1][1]*data[1][1])%M;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
data[i][j]=temp[i][j];
}
result=(sum[0][0]+sum[1][0])%M;
}
printf("%d
",result);
}
return 0;
}
<strong>9. gcd</strong>
long gcd(long x,long y){
return (!y)?x:gcd(y,x%y);
}
<strong>10. </strong>
#include<stdio.h>
struct node_1{
int power;
int intelligence;
int agile;
int index;
};
void sort_1(node_1* node,int down,int up){
for(int i=down;i<up;i++)
for(int j=i+1;j<up;j++){
if(node[i].intelligence<node[j].intelligence){
node_1 temp=node[i];
node[i]=node[j];
node[j]=temp;
}
}
}
void sort_2(node_1* node,int down,int up){
for(int i=down;i<up;i++)
for(int j=i+1;j<up;j++){
if(node[i].agile>node[j].agile){
node_1 temp=node[i];
node[i]=node[j];
node[j]=temp;
}
}
}
int main(){
int i,n=4,j;
node_1 node[500];
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d%d",&node[i].power,&node[i].intelligence,&node[i].agile);
node[i].index=i+1;
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++){
if(node[i].power<node[j].power){
node_1 temp=node[i];
node[i]=node[j];
node[j]=temp;
}
}
int start=0;
int end=1;
while(end<n){
while(node[start].power==node[end].power&&end<n){
end++;
}
if(end-start>1) {
sort_1(node,start,end);
}
start=end;
end++;
}
start=0;
end=1;
while(end<n){
while(node[start].intelligence==node[end].intelligence&&node[start].power==node[end].power&&end<n){
end++;
}
if(end-start>1) {
sort_2(node,start,end);
}
start=end;
end++;
}
for(i=0;i<n;i++) printf("%d
",node[i].index);
return 0;
}
<strong>11. ACM </strong>
#include<stdio.h>
int main(){
int T=2;
scanf("%d",&T);
while(T>0){
int n=3;
scanf("%d",&n);
int ret=1;
int result=0;
while(n){
int temp=n&0x03;
n=n/4;
if(n&0x01){
switch(temp){
case 0:temp=2;break;
case 1:temp=3;break;
case 2:temp=1;break;
case 3:temp=0;break;
default:printf("error
");
}
}
else{
if(temp==2) temp=3;
else if(temp==3) temp=2;
}
result+=temp*ret;
ret*=4;
}
printf("%d
",result);
T--;
}
return 0;
}
<strong>12. </strong>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#define M 5001
#define Max 1000
//#define M 500100
//#define Max 100100
int main(){
//long long phi[M];
long phi[M];
phi[1]=1;
bool prime_bool[M];
long prime[Max];
long len=0;
prime[len++]=2;
long i,j;
for(i=0;i<M;i++) prime_bool[i]=0;
for(i=4;i<M;i+=2) prime_bool[i]=1;
for(i=3;i<M;i+=2)
if(!prime_bool[i]){
prime[len++]=i;
for(j=i*i;j<M;j+=i) prime_bool[j]=1;
}
phi[1] = 1;
for (i = 2; i < M; i++) {
if (!prime_bool[i]) {
phi[i] = i - 1;
continue;
}
for (j = 0; j < len && prime[j] * prime[j] <= i; j++) {
if (i % prime[j] == 0) {
if (i / prime[j] % prime[j] == 0)
phi[i] = prime[j] * phi[i / prime[j]];
else
phi[i] = (prime[j] - 1) * phi[i / prime[j]];
break;
}
}
}
long n;
while(1){
scanf("%ld",&n);
if(n==-1) break;
//long long sum=0;
long sum=0;
for(i=1;i<=n;i++) sum+=phi[i];
sum=2*sum+1;
printf("%lld
",sum);
}
return 0;
}
<strong>13. ， </strong>
#include<stdio.h>
#define Max 65538
int data[Max];
void insert(int s,int t,int step,int left,int right){
if(s==left&&t==right){
data[step]++;
return;
}
if(left==right) return;
int mid=(left+right)/2;
if(mid>=t) insert(s,t,step*2,left,mid);
else if(mid<s) insert(s,t,step*2+1,mid+1,right);
else{
insert(s,mid,step*2,left,mid);
insert(mid+1,t,step*2+1,mid+1,right);
}
}
int search(int i){
int left=0;
int right=65535;
int step=1;
int temp=data[step];
while(left<=right){
int mid=(left+right)/2;
if(i>mid){
step=step*2+1;
left=mid+1;
}
else{
step=step*2;
right=mid;
}
temp+=data[step];
if(left==right){break;}
}
return temp;
}
int main(){
int i;
for(i=0;i<Max;i++) data[i]=0;
int s,t;
for(i=0;i<3;i++){
scanf("%d%d",&s,&t);
insert(s,t,1,0,65535);
}
while(1){
int io;
scanf("%d",&io);
printf("%d
",search(io));
}
return 0;
}
<strong>14. 60=2 2 3 5</strong>
#include <stdio.h>
#include <math.h>
#define N 1000000
int arr[N];
void init()
{
int i,j;
for(i=2;i<sqrt(N);i++)
for(j=2;j<N/i;j++)
arr[i*j]=1;
}
int main()
{
long n;
int i,first;
init();
while(scanf("%ld",&n) && n)
{
for(i=2,first=1;i<=n;i++)
{
if(!arr[i])
while(!(n%i))
{
printf(first ? "%d" : "*%d",i);
n/=i;
first=0;
}
}
printf("
");
}
return 0;
}
<strong>15. </strong>
#include<stdio.h>
#include<math.h>
double cal(double x,int a,int b,int c){
return a*x*x+b*x+c;
}
double max(double a,double b){
return a>b?a:b;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int a1,b1,c1,a2,b2,c2;
scanf("%d%d%d",&a1,&b1,&c1);
scanf("%d%d%d",&a2,&b2,&c2);
double min=max(cal(0,a1,b1,c1),cal(0,a2,b2,c2));
int temp=(b1-b2)*(b1-b2)-4*(a1-a2)*(c1-c2);
bool flag=0;
double compare;
double x1;
if(temp>=0){
if((a1-a2)!=0){
x1=((b2-b1)*1.0+sqrt(temp*1.0))/(2*(a1-a2));
if(x1>0&&x1<1000) flag=1;
double x2=((b2-b1)*1.0-sqrt(temp*1.0))/(2*(a1-a2));
if(x2>0&&x2<1000){
compare=max(cal(x2,a1,b1,c1),cal(x2,a2,b2,c2));
if(compare<min) min=compare;
}
}
else if((b1-b2)!=0){
x1=(c2-c1)*1.0/(b1-b2);
if(x1>0&&x1<1000) flag=1;
}
}
if(flag){
compare=cal(x1,a1,b1,c1);
if(compare<min) min=compare;
}
compare=max(cal(1000,a1,b1,c1),cal(1000,a2,b2,c2));
if(compare<min) min=compare;
x1=(-1.0*b1)/(2*a1);
if(x1>0){
compare=max(cal(x1,a1,b1,c1),cal(x1,a2,b2,c2));
if(compare<min) min=compare;
}
x1=(-1.0*b2)/(2*a2);
if(x1>0){
compare=max(cal(x1,a1,b1,c1),cal(x1,a2,b2,c2));
if(compare<min) min=compare;
}
printf("%.4f
",min);
}
return 0;
}
<strong>16. 6=5+1</strong>
#include<stdio.h>
#include<stdlib.h>
int main(){
long f[101][101];
int n,m;
for(n=1;n<101;n++) f[n][1]=1;
for(n=1;n<101;n++)
for(m=2;m<101;m++){
if(m>n) f[n][m]=f[n][n];
else if(m==n) f[n][m]=1+f[n][m-1];
else if(n-m<m) f[n][m]=f[n-m][n-m]+f[n][m-1];
else f[n][m]=f[n-m][m]+f[n][m-1];
}
int T;
scanf("%d",&T);
while(T>0){
int n;
scanf("%d",&n);
printf("%ld
", f[n][n]);
T--;
}
return 0;
}
<strong>17. </strong>
#include<stdio.h>
int input[10]={1,2,3,4,5,6,7,8,9,10};
void perm(int n)
{
int i;
for(i=0;i<n;i++) printf("%d ",input[i]);
printf("
");
while(1)
{
// , , index
int index=-1;
for(i=n-2;i>=0;i--)
{
if(input[i]<input[i+1])
{
index=i;
break;
}
}
if(index==-1)break; // ，break while
// , input[index] input[index]
int M=0; // M (for swap)
int C; // C
for(int i=n-1;i>=index+1;i--)
{
if(input[i]>input[index])
{
C=i;
M=input[i];
break;
}
}
//cout<<index<<" "<<C<<endl;
// input[index] input[C]
input[C]=input[index];
input[index]=M;
// index ， 7421, 1247，
int len=n-1-index;
for(i=1;i<=len/2;i++)
{
int t=input[index+i];
input[index+i]=input[n-i];
input[n-i]=t;
}
for(i=0;i<n;i++) printf("%d ",input[i]);
printf("
");
}
}
int main()
{
int n;
scanf("%d",&n);
perm(n);
return 0;
}
<strong>18. KMP </strong>
//KMP ！
/*
* Author:puresky
* Date: 2010/12/22
* Version: KMP 4.0,
* Refer to:Handbook of Exact String-Matching Algorithms, Christian Charras & Thierry Lecroq
*/
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#define MAX_PATTERN_LEN 1024
//preprocessing for KMP
void preKMP(const char* t, int next[], int len)
{
int i,j;
next[0] = -1; //Attention: next[0] equals -1 other than 0
i = 0;
j = -1;
while(i < len)
{
while(j > -1 && t[j] != t[i])
j = next[j];
i++, j++;
if(t[j] == t[i])
next[i] = next[j];
else
next[i] = j;
}
}
// KMP, ensure strlen(t) < MAX_PATTERN_LEN
int KMP(const char* s, const char* t)
{
int next[MAX_PATTERN_LEN];
int lens = strlen(s);
int lent = strlen(t);
preKMP(t, next, lent);
int i,j;
i = j = 0;
while(i < lens)
{
while(j > -1 && t[j] != s[i])
j = next[j];
i++, j++;
if(j >= lent) return i - j;
}
return -1;
}
int main(int argc, char** argv)
{
char s[100]="aaaabaaaaaaab";
char t[15]="aaaab";
printf("S:%s
T:%s
", s, t);
int r1 = KMP(s, t); //-1 ，
printf("%d
",r1);
return 0;
}
<strong>19. aXb ， </strong>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
int data[10];
int i,j;
long b=14;
char a[10001];
while(scanf("%s%ld",&a,&b)!=EOF){
for(i=0;i<10;i++) data[i]=0;
int a_length=0;
while(a[a_length++]!='\0');
char temp[2];
temp[0]=a[a_length-2];
temp[1]='\0';
long lipi=b*atoi(temp);
data[lipi%10]++;
lipi/=10;
for(i=a_length-3;i>=0;i--){
temp[0]=a[i];
temp[1]='\0';
lipi=b*atoi(temp)+lipi;
data[lipi%10]++;
lipi/=10;
}
while(lipi){
data[lipi%10]++;
lipi/=10;
}
int data_max=data[0];
for(i=1;i<10;i++){
if(data[i]>data_max){
data_max=data[i];
}
}
bool flag_first=true;
for(i=0;i<10;i++){
if(data[i]==data_max){
if(flag_first){
printf("%d",i);
flag_first=false;
}
else printf(" %d",i);
}
}
printf("
");
}
return 0;
}
<strong>20. kruskal </strong>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Max_len 100005
typedef struct node{
long adjvex;
struct node *next;
long length;
}edgenode;
typedef struct{
int num;
edgenode *link;
}vexnode;
typedef struct{
edgenode *front,*rear;
}linkqueue;
long pre_index[Max_len];
int EMPTY(linkqueue *q){
if(q->front==q->rear) return 1;
else return 0;
}
void ENQUEUEQ(linkqueue *q,long x){
q->rear->next=(edgenode*)malloc(sizeof(edgenode));
q->rear=q->rear->next;
q->rear->adjvex=x;
q->rear->next=NULL;
}
long DEQUEUEQ(linkqueue *q){
long temp;
edgenode *s;
if(EMPTY(q)) return -1;
else{
s=q->front->next;
if(s->next==NULL){
q->front->next=NULL;
q->rear=q->front;
}
else q->front->next=s->next;
temp=s->adjvex;
return temp;
}
}
void quick_sort(long x[],long l,long u){
if(l>=u) return;
long t=x[l];
long i=l;
long j=u+1;
long temp;
while(1){
do{i++;}while(i<=u&&x[i]<t);
do{j--;}while(x[j]>t);
if(i>j)break;
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
temp=x[l];
x[l]=x[j];
x[j]=temp;
quick_sort(x,l,j-1);
quick_sort(x,j+1,u);
}
struct edge{
long fromvex,endvex;
long length;
};
void quick_sort_2(edge x[],int l,int u){
if(l>=u) return;
long t=x[l].length;
int i=l;
int j=u+1;
edge temp;
while(1){
do{i++;}while(i<=u&&x[i].length<t);
do{j--;}while(x[j].length>t);
if(i>j)break;
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
temp=x[l];
x[l]=x[j];
x[j]=temp;
quick_sort_2(x,l,j-1);
quick_sort_2(x,j+1,u);
}
int main(){
int m,T;
int case_count=1;
scanf("%d",&T);
while(T--){
printf("Case #%d:
",case_count);
case_count++;
vexnode ga[Max_len];
long triangle[Max_len];
int sign[Max_len];
edge data[Max_len];
int G[Max_len];
long i,j,k,n,l,i1;
scanf("%ld",&n);
edgenode *s;
for(i=0;i<=n;i++) {ga[i].link=NULL;ga[i].num=0;}
for(i=0;i<=n;i++) {sign[i]=0;G[i]=i;}
for(i=0;i<n-1;i++){
scanf("%ld%ld%ld",&data[i].fromvex,&data[i].endvex,&data[i].length);
}
quick_sort_2(data,0,n-2);
j=0;
i=0;
while(j<n-1){
k=data[i].fromvex;
l=data[i].endvex;
sign[i]=1;
if(G[k]==G[l]) sign[i]=2;
else{
s=(edgenode*)malloc(sizeof(edgenode));
s->adjvex=data[i].endvex;
s->next=ga[data[i].fromvex].link;
s->length=data[i].length;
ga[data[i].fromvex].link=s;
ga[data[i].fromvex].num++;
s=(edgenode*)malloc(sizeof(edgenode));
s->adjvex=data[i].fromvex;
s->next=ga[data[i].endvex].link;
s->length=data[i].length;
ga[data[i].endvex].link=s;
ga[data[i].endvex].num++;
j++;
for(i1=0;i1<n;i1++)
if(G[i]==G[l]) G[i]=G[k];
}
i++;
}
scanf("%d",&m);
int j1;
for(j1=0;j1<m;j1++){
long s1,t;
scanf("%ld%ld",&s1,&t);
linkqueue *q;
q=(linkqueue*)malloc(sizeof(linkqueue));
q->front=(edgenode*)malloc(sizeof(edgenode));
q->front->next=NULL;
q->rear=q->front;
//printf("%d
",s1);
int visit[Max_len];
for(i=0;i<=n;i++) visit[i]=0;
visit[s1]=1;
ENQUEUEQ(q,s1);
int find_t=0;
for(i=0;i<=n;i++) pre_index[i]=-1;
while(!EMPTY(q)){
i=DEQUEUEQ(q);
int n_count=ga[i].num;
s=ga[i].link;
int q_count=0;
while(q_count<n_count){
if(visit[s->adjvex]!=1){
pre_index[s->adjvex]=i;
//printf("%d->%d
",i,s->adjvex);
if(s->adjvex==t){
find_t=1;
goto next_1;
}
visit[s->adjvex]=1;
ENQUEUEQ(q,s->adjvex);
}
s=s->next;
q_count++;
}
}
next_1: int find_triangle=0;
if(find_t){
long triangle_num=0;
long index=s->adjvex;
while(index!=s1){
s=ga[pre_index[index]].link;
int n_count=ga[pre_index[index]].num;
int q_count=0;
while(q_count<n_count){
if(s->adjvex==index) break;
else s=s->next;
q_count++;
}
triangle[triangle_num]=s->length;
//printf("%d
",s->length);
triangle_num++;
index=pre_index[index];
}
if(triangle_num>2){
quick_sort(triangle,0,triangle_num-1);
for(i=0;i<triangle_num;i++)
for(j=i+1;j<triangle_num;j++)
for(k=j+1;k<triangle_num;k++){
if(triangle[k]<triangle[i]+triangle[j]){find_triangle=1;break;}
}
}
}
if(find_triangle) printf("Yes
");
else printf("No
");
}
}
return 0;
}
<strong>21. </strong>
// o(nm)
#include<stdio.h>
#include <iostream>
using namespace std;
const int MAXN = 1001 ,MAXM = 1001 ;
int n1,n2,m,ans; //n1,n2 , 1..n1,1..n2 ,m
bool g[MAXN][MAXM]; // G g[x][y]
bool y[MAXM]; //Y i
int link[MAXM]; //link[y] y x
bool find(int x) // X x
{
int i;
for (i = 1 ;i <= n2;i++)
if (g[x][i] && !y[i]) // i x
{
y[i] = true ;
if (link[i] == -1 || find(link[i])) // i i
{
link[i] = x;
return true ;
}
}
return false ;
}
int main()
{
int a,b,i;
memset(g,0 ,sizeof (g));
memset(link,-1 ,sizeof (link));
ans = 0 ;
scanf("%d%d%d" ,&n1,&n2,&m);
for (i = 1 ;i <= m;i++)
{
scanf("%d%d" ,&a,&b);
g[a][b] = true ;
}
for (i = 1 ;i <= n1;i++)
{
memset(y,0 ,sizeof (y));
if (find(i))
ans++;
}
printf("%d
" ,ans);
return 0 ;
}
<strong>
22. Dijkstra </strong>
#include<stdio.h>
#define N 100
#define Max 10000 //
int D[N]; // v
int p[N],s[N];
int dist[N][N]; //
void Dijkstra(int v,int n){
int i,j,k,v1,min,max=10000;
v1=v;
for(i=0;i<n;i++){
D[i]=dist[v1][i];
if(D[i]!=Max) p[i]=v1+1;
else p[i]=0;
s[i]=0;
}
s[v1]=1;
for(i=0;i<n;i++){
min=10001;
for(j=0;j<n;j++)
if((!s[j])&&(D[j]<min)){
min=D[j];
k=j;
}
s[k]=1;
for(j=0;j<n;j++)
if((!s[j])&&(D[j]>D[k]+dist[k][j])){
D[j]=D[k]+dist[k][j];
p[j]=k+1;
}
}
int pre;
for(i=0;i<n;i++){
printf("%d %d",D[i],i);
pre=p[i];
while((pre!=0)&&(pre!=v+1)){
printf("<-%d",pre-1);
pre=p[pre-1];
}
printf("<-%d
",v);
}
}
int main(){
int data[6][6]={{0,6,9,8,10000,10000},{18,0,7,10000,10000,10},{9,10000,0,15,10000,10000},{10000,10000,12,0,10000,10000},{10000,10000,4,10000,0,10000},{24,5,10000,25,10000,0}};
int n=6,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dist[i][j]=data[i][j];
Dijkstra(4,n);
return 0;
}
<strong>23. SPFA </strong>
#include<iostream>
#include <vector>
#include <queue>
using namespace std;
const int SIZE = 100010;
const int INF = 0x3f3f3f3f;
int u[4*SIZE], w[4*SIZE], v[4*SIZE], next[4*SIZE]; // 4*SIZE
int first[SIZE], d[SIZE];
int sum[SIZE];
int n, m; //n ，m 。
int spfa(int src)
{
queue<int> q;
bool inq[SIZE] = {0};
for(int i = 0; i <= n; i++) d[i] = (i == src)? 0:INF;
q.push(src);
while(!q.empty())
{
int x = q.front();
q.pop();
inq[x] = 0;
for(int e = first[x]; e!=-1; e = next[e])
if(d[v[e]] > d[x]+w[e])
{
d[v[e]] = d[x]+w[e];
if(!inq[v[e]])
{
inq[v[e]] = 1;
if(++sum[v[e]] > n) //
{
return -1;
}
q.push(v[e]);
}
}
}
if(d[n] == INF) return -2;
else return d[n]; //d[i] src i ，d[n] src n
}
int main()
{
int i;
memset(first, -1, sizeof(first));
scanf("%d%d",&n,&m);
for(i = 0; i < n; i++)
{
scanf("%d%d%d", &u[i], &v[i], &w[i]);
next[i] = first[u[i]];
first[u[i]] = i;
}
int min_path=spfa(1); // ， ， 1 n ，0
printf("%d
",min_path);
return 0;
}
/*
1 2 7
2 3 -5
1 3 5
d[1]=0
d[2]=7
d[3]=2
*/
<strong>24. Floyd </strong>
#include<stdio.h>
#define N 101
#define Max 10000
int path[N][N];
int A[N][N];
int dist[N][N];
void Floyd(int n){
int i,j,k,next,max=10000;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(dist[i][j]!=Max) path[i][j]=i+1;
else path[i][j]=0;
A[i][j]=dist[i][j];
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j])){
A[i][j]=A[i][k]+A[k][j];
path[i][j]=path[k][j];
}
for(i=0;i<n;i++)
for(j=0;j<n;j++){
printf(" %d %d",A[i][j],j);
int pre=path[i][j];
while((pre!=0)&&(pre!=i+1)){
printf("<-%d",pre-1);
pre=path[i][pre-1];
}
printf("<-%d
",i);
}
}
int main(){
int data[6][6]={{0,6,10000,8,10000,10000},{18,0,7,10000,10000,10},{9,10000,0,15,10000,10000},{10000,10000,12,0,10000,10000},{10000,10000,4,10000,0,10000},{24,5,10000,25,10000,0}};
int n=6,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dist[i][j]=data[i][j];
Floyd(n);
return 0;
}
<strong>25. SAP </strong>
#include<stdio.h>
#include <iostream>
#include <queue>
#define msize 1024 //
using namespace std;
int d[msize]; //
int r[msize][msize]; // ，
int num[msize]; //num[i] i
int pre[msize]; //
int n,m,s,t; //m ，n ， s t
//
void ini_d() //BFS ， t 0
{
int k;
queue<int>Q;
memset(d,1,sizeof(d)); // , for
memset(num,0,sizeof(num));
Q.push(t);
d[t]=0; // 0
num[0]=1;
while (!Q.empty())
{
k=Q.front(),Q.pop();
for (int i=0;i<m;i++) //
{
if (d[i]>=m&&r[i][k]>0) // ， frontint
{
d[i]=d[k]+1;
Q.push(i);
num[d[i]]++;
}
}
}
}
int findAlowArc(int i) // i
{
int j;
for (j=0;j<m;j++) if (r[i][j]>0&&d[i]==d[j]+1) return j;
return -1;
}
int min(int a,int b){
return a>b?b:a;
}
int reLable(int i) //
{
int mm=INT_MAX;
for (int j=0;j<m;j++)
if (r[i][j]>0) mm=min(mm,d[j]+1);
return mm==INT_MAX?m:mm;
}
int maxFlow(int s,int t) // s
{
int flow=0,i=s,j;
int delta; //
memset(pre,-1,sizeof(pre));
while (d[s]<m)
{
j=findAlowArc(i);
if (j>=0)
{
pre[j]=i;
i=j; //
if (i==t) //
{
delta=INT_MAX;
for (i=t;i!=s;i=pre[i]) delta=min(delta,r[pre[i]][i]); //
for (i=t;i!=s;i=pre[i]) r[pre[i]][i] -= delta, r[i][pre[i]] += delta; //
flow += delta;
}
}
else
{
int x=reLable(i); //
num[x]++;
num[d[i]]--;
if (num[d[i]]==0) return flow; //
d[i]=x;
if (i!=s) i=pre[i];
}
}
return flow;
}
int main(){
int i;
m=6;
n=7;
scanf("%d%d",&m,&n);
for(i=0;i<n;i++){
int a,b,vex;
scanf("%d%d%d",&a,&b,&vex);
r[a][b]=vex; // 0
//r[a-1][b-1]=vex; // 1
}
s=0; //source node
t=5; //end node
ini_d();
printf("%d
",maxFlow(s,t));
for(i=0;i<m;i++) printf("%d->%d
",pre[i],i);
return 0;
}
<strong>26. </strong>
#include<iostream>
using namespace std;
#define Max 1000
int inf=10000;
int n, ans;
int cap[Max][Max], pre[Max];
int cost[Max][Max], dis[Max];
int que[Max];
bool vis[Max];
bool spfa(){ // 0， n。
int i, head = 0, tail = 1;
for(i = 0; i <= n; i ++){
dis[i] = inf;
vis[i] = false;
}
dis[0] = 0;// dis
que[0] = 0;
vis[0] = true; //u
while(tail != head){ // 。
int u = que[head];
for(i = 0; i <= n; i ++)
if(cap[u][i] && dis[i] > dis[u] + cost[u][i]){ // ， 。
dis[i] = dis[u] + cost[u][i];
pre[i] = u;
if(!vis[i]){
vis[i] = true;
que[tail ++] = i;
if(tail == Max) tail = 0;
}
}
vis[u] = false;
head ++;
if(head == Max) head = 0;
}
if(dis[n] == inf) return false;
return true;
}
int min(int a,int b){
return a>b?b:a;
}
void end(){
int i, sum = inf;
for(i = n; i != 0; i = pre[i])
sum = min(sum, cap[pre[i]][i]);
for(i = n; i != 0; i = pre[i]){
cap[pre[i]][i] -= sum;
cap[i][pre[i]] += sum;
ans += cost[pre[i]][i] * sum; // cost[][] ， 。
}
//printf("ans: %d
",ans);
}
int main(){
int m;
ans = 0;
scanf("%d%d",&n,&m);//n m
int i,u,v,ca,co;
for(i=0;i<m;i++){
scanf("%d%d%d%d",&u,&v,&ca,&co);
cap[u][v]=ca;
cost[u][v]=co;
}
n--; // 0...n-1，n-1
while(spfa()){
end(); // 0， n。
}
printf("ans: %d
",ans);
return 0;
}
<strong>27. ：kruskal ，
</strong>
#include<stdio.h>
typedef struct{
int fromvex,endvex;
int length;
int sign;
}edge;
#define N 101
edge tree[N];
int G[N];
void quick_sort_2(edge x[],int l,int u){
if(l>=u) return;
int t=x[l].length;
int i=l;
int j=u+1;
edge temp;
while(1){
do{i++;}while(i<=u&&x[i].length<t);
do{j--;}while(x[j].length>t);
if(i>j)break;
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
temp=x[l];
x[l]=x[j];
x[j]=temp;
quick_sort_2(x,l,j-1);
quick_sort_2(x,j+1,u);
}
void kruskal(int n,int e){ //n ,e
int i,i1,j,k,l;
for(i=0;i<=n;i++)
G[i]=i;
for(i=0;i<e;i++){
scanf("%d %d %d",&tree[i].fromvex,&tree[i].endvex,&tree[i].length);
tree[i].sign=0;
}
quick_sort_2(tree,0,e-1);
i=0;
j=0;
while(j<n-1){
k=tree[i].fromvex;
l=tree[i].endvex;
tree[i].sign=1;
if(G[k]==G[l]) tree[i].sign=2;
else{
j++;
printf("%d
",tree[i].length);
for(i1=0;i1<n;i1++){
if(i1==l) continue;
if(G[i1]==G[l]) G[i1]=G[k];
}
G[l]=G[k];
}
i++;
}
}
int main(){
int n,e;
scanf("%d%d",&n,&e);
kruskal(n,e);
return 0;
}
<strong>28. ：prime ， </strong>
#include<stdio.h>
typedef struct{
int fromvex,endvex;
float length;
}edge;
#define N 100
float dist[N][N];
edge T[N-1]; // ， 0~n-2，
void Prime(int i,int n){
int j,k,m,v,min,max=10000;
float d;
edge e;
v=i;
for(j=0;j<n-1;j++){
T[j].fromvex=v;
if(j>=v){T[j].endvex=j+1;T[j].length=dist[v][j+1];}
else{T[j].endvex=j;T[j].length=dist[v][j];}
}
for(k=0;k<n-1;k++){
min=max;
for(j=k;j<n-1;j++)
if(T[j].length<min){min=T[j].length;m=j;}
e=T[m];T[m]=T[k];T[k]=e;
v=T[k].endvex;
for(j=k+1;j<n-1;j++){
d=dist[v][T[j].endvex];
if(d<T[j].length){
T[j].length=d;
T[j].fromvex=v;
}
}
}
}
int main(){
float data[6][6]={{10000,10,10000,10000,19,21},{10,10000,5,7,10000,11},{10000,5,10000,6,10000,10000},{10000,7,6,10000,18,14},{19,10000,10000,18,10000,33},{21,11,10000,14,33,10000}};
int n=6,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dist[i][j]=data[i][j];
Prime(0,n);
for(i=0;i<n-1;i++) printf("%d->%d : %f
",T[i].fromvex,T[i].endvex,T[i].length);
return 0;
}