poj 3565 uva 1411 Ants KM算法求最小权

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #define N 110
 6 struct sss
 7 {
 8     int x,y;
 9 }white[N],black[N];
10 int n,vx[N],vy[N],fa[N];
11 double w[N][N],px[N],py[N],str[N];
12 double dis(int i,int j)
13 {
14     return sqrt((double)(black[i].x-white[j].x)*(black[i].x-white[j].x)+(double)(black[i].y-white[j].y)*(black[i].y-white[j].y));
15 }
16 int find(int now)
17 {
18     int i,j,k;
19     if (now==0)
20       return 1;
21     vx[now]=1;
22     for (i=1;i<=n;i++)
23     {
24       if (!vy[i]&&fabs(px[now]+py[i]-w[now][i])<0.00001)
25       {
26           vy[i]=1;
27           if (fa[i]==0||find(fa[i]))
28           {
29               fa[i]=now;
30               return 1;
31           }
32       }
33       else
34         if (str[i]>px[now]+py[i]-w[now][i])
35           str[i]=px[now]+py[i]-w[now][i];
36     }
37     return 0;
38 }
39 void KM()
40 {
41     int i,j,k,x,y,z;
42     double na;
43     memset(fa,0,sizeof(fa));
44     for (i=1;i<=n;i++)
45     {
46         memset(str,0x7f,sizeof(str));
47         while (1)
48         {
49             memset(vx,0,sizeof(vx));
50             memset(vy,0,sizeof(vy));
51             if (find(i))
52               break;
53             na=0x7f;
54             for (j=1;j<=n;j++)
55               if (!vy[j]&&na>str[j])
56                 na=str[j];
57             for (j=1;j<=n;j++)
58             {
59                 if (vx[j])
60                   px[j]-=na;
61                 if (vy[j])
62                   py[j]+=na;
63                 else
64                   str[j]-=na;
65             }
66         }
67     }
68 }
69 int main()
70 {
71     int i,j,k,x,y,z;
72     z=0;
73     while(scanf("%d",&n)!=EOF)
74     {
75         if (z)
76           printf("\n");
77         else
78           z=1;
79         for (i=1;i<=n;i++)
80           px[i]=-100000;
81         memset(py,0,sizeof(py));
82         for (i=1;i<=n;i++)
83           scanf("%d%d",&white[i].x,&white[i].y);
84         for (i=1;i<=n;i++)
85           scanf("%d%d",&black[i].x,&black[i].y);
86         for (i=1;i<=n;i++)
87           for (j=1;j<=n;j++) 
88           {
89               w[i][j]=-dis(i,j);
90               if (px[i]<w[i][j])
91                 px[i]=w[i][j];
92           }
93         KM();
94         for (i=1;i<=n;i++)
95           printf("%d\n",fa[i]);
96     }
97 }