package wsclient.domain;
import java.io.*;
import java.util.*;
public class Progress {
static int[] flagleave;
static int[] d;
static int Short_Tree[][];
static int p[][];
static int leave[];
static int dist[];
static double weight[];
static int bubble[];
static double[][] edgeweight;
static double[][] edgew;
static void Short_path( int[][] G,int n ,int v0){
int w,i,j,min;
int num [];
int v=v0;
int finall[];
finall=new int [n];
d =new int[n];
num=new int[n];
flagleave=new int[n];
Short_Tree=new int[n][n];
p=new int[n][n];
for(i=0;i<n;i++) {
flagleave[i]=1;
num[i]=0;
}
for(int q=0;q<n;q++){
finall[ q]=0;
d[q]=G[v0][q];
flagleave[q]=1;
for(int z=0;z<n;z++){
Short_Tree[q][z]=0;
p[q][z]=n;
}
if (d[q]<9999&&d[q]>0)
p[q][0]=v0;
}
d[v0]=0;
finall[v0]=1;
for(i=1;i<n;i++){
min=9999;
for(w=0;w<n;w++)
if(finall[w]==0)
if(d[w]<min){
v=w;
min=d[w];
}
finall[v]=1;
if(v!=v0){
for(j=0;j<=num[v];j++){
flagleave[p[v][j]]=0;
Short_Tree[p[v][j]][v]=1;
}
}
for(w=0;w<n;w++)
if(finall[w]==0&&(min+G[v][w])<d[w]){
num[w]=0;
d[w]=min+G[v][w];
p[w][num[w]]=v;
}
else if(finall[w]==0&&(min+G[v][w])==d[w]){
p[w][++num[w]]=v;
}
}
}
static void findleave (int n){
int i=0,j=0;
int a=0;
while(i<n){
if(flagleave[i]==1)
a++;
i++;
}
System.out.println("有"+a+"个叶子节点");
leave=new int[a];
i=0;
while(i<n){
if(flagleave[i]==1)
leave[j++]=i;
i++;
}
System.out.println("分别是叶子节点");
for(i=0;i<a;i++)
System.out.print(leave[i]+" ");
}
int retu_m (int n){
int i;
int m=n-1;
for(i=0;i<n;i++){
if (d[i]==9999)
m=--n ;
}
return m;
}
static void distAndweight(int v0, int n) {
int Q[] = new int[n];
int top = 0, rear = 0;
int topitem;
weight = new double[n];
dist = new int[n];
for (int i = 0; i < n; i++) {
weight[i] = 0.0;
Q[i] = 0;
dist[i] = 0;
}
dist[v0] = 0;
weight[v0] = 1;
for (int i = 0; i < n; i++) {
if (Short_Tree[v0][i] == 1) {
dist[i] = 1;
weight[i] = 1;
Q[rear++] = i;
}
} while (top != rear) {
topitem = Q[top];
top++;
for (int i = 0; i < n; i++) {
if (Short_Tree[topitem][i] == 1) {
if (d[i]!=9999 && dist[i] == 0) {
dist[i] = dist[topitem] + 1;
weight[i] = weight[topitem];
Q[rear++] = i;
} else if (dist[i] == dist[topitem] + 1) {
weight[i] = weight[topitem] + weight[i];
} else if (dist[i] != 0 && dist[i] < dist[topitem] + 1) {
dist[i] = dist[i];
}
}
}
} //while
}
void bubblesort( int n) {
int i, j;
bubble = new int[n];
for (i = 0; i < n; i++) {
bubble[i] = dist[i];
}
int flag = 1;
int temp;
i = n - 2;
while (i >= 0 && flag == 1) {
flag = 0;
for (j = 0; j <= i; j++) {
if (bubble[j] < bubble[j + 1]) {
temp = bubble[j];
bubble[j] = bubble[j + 1];
bubble[j + 1] = temp;
flag = 1;
}
}
i--;
} //while
}
int ret_dist (int n,int v0){
int max=0;
int w=v0;
for(int i=0;i<n;i++)
if(dist[i]>max){
max=dist[i];
w=i;
}
return w;
}
void caledgw(int n,int[][]W) {
int[] flag;
int q=0;
edgeweight = new double[n][n];
flag=new int[n];
for (int i = 0; i < n; i++) {
flag[i]=0;
for (int j = 0; j < n; j++) {
edgeweight[i][j] = 0.0;
}
}
for (int i = 0; i < n; i++) {
for(int j=0;j<n;j++){
if (bubble[i]==dist[j]){
if(flagleave[j]==1&&flag[j]==0){
for(int w=0;w<n;w++)
if(Short_Tree[w][j]==1){
// System.out.print(w+" ");
edgeweight[w][j]=weight[w] /weight[j];
flag[j]=1;
}
}
if(flagleave[j]==0&&flag[j]==0) {
for(int w=0;w<n;w++){
if (Short_Tree[w][j]==1){
q=0;
while(q<n){
if(Short_Tree[j][q]==1)
edgeweight[w][j]=edgeweight[w][j]+edgeweight[j][q];
q++;
}
edgeweight[w][j]=(edgeweight[w][j]+1)*(weight[w]/weight[j]);
flag[j]=1;
}
}
}
}
}
}
System.out.println("gggggggggggggggggggggggggggggggg");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
//123edgeweight[i][j]= edgeweight[i][j];
System.out.println("22222222222gggggggg"+W[i][j]);
System.out.println("edgeweight["+i+"]["+j+"]"+edgeweight[i][j]);
}
}
int Del_small(int n ,int[][] G,int eb){
double max=0;
int i,j,a=0,b=0;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(edgew[i][j]>max){
max=edgew[i][j];
a=i;
b=j;
}
}
}
//W[a][b]--;
// W[b][a]--;
//if(W[a][b]==0) {
G[a][b]=9999;
eb--;
G[b][a]=9999;
// }
System.out.println();
return eb;
}
int BFSTra(int[][] G,int n,int[][] M,int[] yuan){
int Q[] = new int[n];
int cheng=0;
int top = 0, rear = 0;
int topitem;
int she=0;
int count1=n;
int count2=0;
int visited[]=new int[n];
// int M[][]=new int[n][n];
for(int i=0;i<n;i++) {
visited[i]=0;
yuan[i]=0;
}
for(int i=0;i<n;i++){
if(visited[i]==0){
cheng=0;
she++;
visited[i]=1;
if(she==1){count1=n;count2=0;}
else {
//System.out.println("yuan["+a+"]="+yuan[a]);
count2=count2+yuan[she-2];
count1=count1-yuan[she-2];
}
M[she-1]=new int[count1];
for(int t=0;t<count1;t++)
M[she-1][t]=1;
M[she-1][cheng++]=i;
yuan[she-1]++;
Q[rear++] = i;
}
while (top != rear) {
topitem = Q[top];
top++;
for (int j = 0; j < n; j++) {
if((G[topitem][j]!=9999||G[j][topitem]!=9999)&&visited[j]==0){
visited[j]=1;
M[she-1][cheng++]=j;
yuan[she-1]++;
Q[rear++] = j;
}
}
}
}
System.out.println("ya cishi she="+she);
return she;
}
int BFSTra3(int[][] A,int n,String[][] oplist){
int Q[] = new int[n];
int cheng=0;
int top = 0, rear = 0;
int topitem;
int she=0;
int count1=n;
int count2=0;
int visited[]=new int[n];
int M[][]=new int[n][ ];
int[] yuan=new int[n];
fileout ft=new fileout("jieguo");
for(int i=0;i<n;i++) {
visited[i]=0;
yuan[i]=0;
}
for(int i=0;i<n;i++){
if(visited[i]==0){
cheng=0;
she++;
visited[i]=1;
if(she==1){count1=n;count2=0;}
else {
//System.out.println("yuan["+a+"]="+yuan[a]);
count2=count2+yuan[she-2];
count1=count1-yuan[she-2];
}
M[she-1]=new int[count1];
for(int t=0;t<co
- 1
- 2
- 3
- 4
- 5
- 6
前往页