Description

　　郵局需要你來幫助他們?yōu)槟硞€郵遞員設(shè)計出一條能夠穿過那遙遠(yuǎn)鄉(xiāng)村的所有村子和小路至少一次的郵路（輸入數(shù)據(jù)將會保證這么一條路是一定存在的）。
　　但是，每條路線都是有一個花費的。各個村子里的村民希望郵遞員到達(dá)他們村子的時間越早越好。因此，各個村子里的人們采用了一些措施：假設(shè)第i號村子是郵遞員在他的郵遞路線上到達(dá)的第k個不同的村子。如果k<=w( i )，那么這個村子的村民就會付給郵局w( i )-k歐元。當(dāng)然，如果k>w(i)，郵局也同意付k- w( i )歐元給這個村子，重復(fù)經(jīng)過村子不重復(fù)收費。此外，郵遞員每經(jīng)過一條小路，郵局也要付給郵遞員1歐元作為補貼。
　　現(xiàn)在有n個村子，編號依次為1到n。郵局就位于1號村子，因此郵遞員的傳遞路線從這里開始，也從這個村子結(jié)束。能夠離開每個村子的路口的數(shù)目一定是2，4或者8。這里允許出現(xiàn)同樣的村子間存在多條小路，或者某條小路構(gòu)成了一個自環(huán)的情況。
　　你的任務(wù)是設(shè)計一個路線使得郵局賺的錢最多(或者說賠的錢最少。如果有多種最優(yōu)解，輸出字典序最小的。

Input

　　第一行：兩個整數(shù)n，m，分別表示村子的數(shù)量和小路的數(shù)量。
　　接下來n行，每行一個整數(shù)：w(i)(1≤w(i)<1 000)
　　接下來m行，每行兩個整數(shù)u，v，表示這條小路連接的村子的編號。

Output

　　第一行：一個整數(shù)k，你的程序所設(shè)計的路徑的長度
　　第二行：k+1個整數(shù)，v1，v2…vk+l，每個數(shù)之間用一個空格隔開，表示你設(shè)計的路徑所經(jīng)過的村子的編號，其中需要滿足v1=vk+1=1

Sample Input

6 7
1
7
4
10
20
5
2 4
l 5
2 l
4 5
3 6
1 6
1 3

Sample Output

7
1 2 4 5 1 3 6 1

Data Constraint

　
對于30％的數(shù)據(jù)，有N<=20
對于100%的數(shù)據(jù)，有N<=200;

Solution

• 顯然，權(quán)值是沒有任何用處的，怎么走答案都不會變。

• 于是問題就變成了如何求最小字典序了，觀察到一個點的出邊都是偶數(shù)（2，4，8）

• 那么這就是經(jīng)典的歐拉回路，可以貪心地求解。

• 從小到大遞歸下去，退棧時加入答案，最后將答案倒序輸出即可， O(N2) 解決。

Code

#include<cstdio> using namespace std; const int N=201; int n,m; int ans[N*8],a[N][N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void dfs(int x) {for(int i=1;i<=n;i++)if(a[x][i]){a[x][i]--,a[i][x]--;dfs(i);}ans[++ans[0]]=x; } int main() {n=read(),m=read();for(int i=1;i<=n;i++) read();for(int i=1;i<=m;i++){int x=read(),y=read();a[x][y]++,a[y][x]++;}dfs(1);printf("%d\n",ans[0]-1);for(int i=ans[0];i;i--) printf("%d ",ans[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 1319. 邮递员的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。