bon

C++博客 :: 首頁 :: 聯(lián)系 :: 聚合

:: 管理

46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用鏈接

留言簿(2)

我參與的團隊

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

PKU 2941

PKU 2941
這道題需要動一下腦筋，屬于數(shù)學(xué)題。
問題描述：給一個n×n的矩陣，如果從每行各拿出一個元素，且這些元素的列指標都不同，即

$a_{1j_{1}},a_{2j_{2}},\dots,a_{nj_{n}}$

其中 $j_{1}, j_{2}, \dots , j_{n}$ 是 $1,2,\dots,n$ 的一個排列。
如果任何這樣一個 $a_{1j_{1}},a_{2j_{2}},\dots,a_{nj_{n}}$ 元素的和都相等，則稱這個矩陣是homogeneous的。

題目要求任給一個n維矩陣,1<=n<=1000，判斷它是否是homogeneous的。

如果直接做，即求出所有的 $a_{1j_{1}},a_{2j_{2}},\dots,a_{nj_{n}}$ 然后求和，這樣的復(fù)雜度為n!，這是無法接受的。

下面給出一個算法，能在 $O(n^{3})$ 時間內(nèi)判斷出來。設(shè)n維矩陣A，現(xiàn)為A加上一行跟一列，使A變成n+1維的。

Theorem 1

若n維矩陣A是homogeneous的，則劃去A的任一行與任一列，剩下的n-1維矩陣是homogeneous的。

Proof
設(shè)劃去的是第x行第y列，剩下的矩陣若不是homogeneous的，則存在 $a_{1j_{1}},a_{2j_{2}},\dots,a_{nj_{n-1}}$ 與 $a_{1k_{1}},a_{2k_{2}},\dots,a_{nk_{n-1}}$ ，這兩個序列的和不等，那么都加上 $a_{x,y}$ ，可以得到矩陣A的兩個序列，這兩個序列的和不等，即A不是homogeneous的，與假設(shè)矛盾。

Theorem 2
若Homogeneous的A增廣后的矩陣B是Homogeneous的，則對于A中任意元素 $a_{ij}$ ，必有 $a_{ij}+a_{n+1,n+1}=a_{i,n+1}+a_{n+1,j}$

Proof
這個等式的意義是在A取元素 $a_{ij}$ ，在新矩陣取 $a_{n+1,n+1}$ ，其余任取，這么一個序列的和必須等于在新矩陣中取 $a_{i,n+1}$ 跟 $a_{n+1,j}$ ，其余任取所得的序列的和。注意到任取那部分是在A劃去行i，列j后的子矩陣中取的。由于B是Homogeneous，任何合法序列的和都相等，若題設(shè)的等式不成立，則任取這一部分也不相等（這樣才可能使得所有B包含 $a_{ij}$ 的序列的和都相等）。但A是Homogeneous的，任取這一部分不可能不等，矛盾。

有了上面的定理2，算法就很簡單，看下面的代碼：

1 #include <iostream>
2
3 using namespace std;
4
5 int a[1001][1001];
6
7 int main()
8 {
9     int i,j,k,n;
10     while(scanf("%d",&n) && n!=0){
11         for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]);
12         int flag=0;
13         for(i=1;i<n && !flag;i++){
14             for(j=0;j<i && !flag;j++){
15                 for(k=0;k<i && !flag;k++){
16                     if(a[i][i]+a[j][k] != a[i][k]+a[j][i]) flag=1;
17                 }
18             }
19         }
20         if(flag==1) printf("not homogeneous\n");
21         else printf("homogeneous\n");
22     }
23     return 1;
24 }

posted on 2008-03-14 16:34 bon 閱讀(427) 評論(0) 編輯收藏引用所屬分類: Programming Contest

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: KMP (2) KMP算法 poj 2748 poj 3437 pku 3349 poj 3340 poj 3307 pku 3421 PKU 2833 PKU 3264

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

bon