HDU3118-利用二進(jìn)制狀態(tài)和二分圖的性質(zhì)（好題）

2019-11-08 19:24:43

字體：大中小

供稿：網(wǎng)友

Arbiter

Time Limit: 1000/1000 MS (java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1242 Accepted Submission(s): 609PRoblem DescriptionArbiter is a kind of starship in the StarCraft science-fiction series. The Arbiter-class starship is a Protoss warship specializing in providing psychic support. Arbiters were crewed exclusively by Judicators; unlike other warships that were manned predominantly by Templar. The Judicator used the Arbiter as a base to provide support using space-time manipulation.Arbiters could weaken space-time, tearing rifts in the fabric of space-time, creating a vortex linking another location to the Arbiter’s location. This could be used to move personnel over long distances between stars.In the meantime of widely used Arbiter to transfer, KMXS, the captain of one Arbiter, was warning that some person had got a serious mental disorder after the trip on his Arbiter. By using mice as model animals, he found the sake, it’s because of chirality!Every person has chirality, either left-handed or right-handed. Actually all the persons must live with the food which has the same chirality. When one person took Arbiter from one star to another one, his chirality will be changed (from left-handed to right-handed or from right-handed to left-handed). If a person took a long trip and finally got back to his own star, however, his chirality might be changed to the opposite state other than his original, which would cause fatal mental disorder, or even death. KMXS has the channels map among the starts and he need to prohibit minimum number of channels from traveling so that wherever a person starts his traveling from when he gets his original star he’ll be safe. KMXS turns to your help. InputThe first line of input consists of an integer T, indicating the number of test cases.The first line of each case consists of two integers N and M, indicating the number of stars and the number of channels. Each of the next M lines indicates one channel (u, v) which means there is a bidirectional channel between star u and star v (u is not equal to v). OutputOutput one integer on a single line for each case, indicating the minimum number of channels KMXS must prohibit to avoid mental disorder.Constraints0 < T <= 100 <= N <= 15 0 <= M <= 3000 <= u, v < N and there may be more than one channel between two stars. Sample Input

13 30 11 22 0 Sample Output1 Source2009 Asia Wuhan Regional Contest Online
題目大意：
                 給你一張有向圖，問(wèn)你最少刪除的邊數(shù)使得圖中沒(méi)有奇數(shù)環(huán)，即環(huán)的點(diǎn)數(shù)為奇數(shù)（1除外）
題目思路：
                首先我們看看二分圖的定義：無(wú)向圖G=<V,E>為二分圖的充要條件是G的所有回路的長(zhǎng)度均為偶數(shù)。
                 所以我們可以利用二分圖的性質(zhì)來(lái)做這題，首先我們可以利用二進(jìn)制的來(lái)枚舉他的所有二分圖的組合，二進(jìn)制中1和0分別屬于不同的集合，然后我們?cè)诿杜e同一集合當(dāng)中的點(diǎn)是否存在邊，如果存在邊就刪掉該邊，然后在記錄刪除的次數(shù)，最后取個(gè)最小值就是我們要求的答案
AC代碼：
#include<cstring>#include<cstdio>#define min(x,y) (x<y?x:y)int mp[20][20];int n,m;int sove(int k){    int num=0;    for(int i=0;i<n;i++){        for(int j=i+1;j<n;j++){            if((1&(k>>i))==(1&(k>>j))&&mp[i][j])num+=mp[i][j];    //枚舉所有同一集合的點(diǎn)的組合看是否有邊        }    }    return num;}int main(){    int t;scanf("%d",&t);    while(t--){        memset(mp,0,sizeof(mp));        scanf("%d%d",&n,&m);        while(m--){            int u,v;scanf("%d%d",&u,&v);            mp[u][v]++,mp[v][u]++;       //記錄邊出現(xiàn)的次數(shù)        }        int ans = 1e8;        for(int i=1;i<(1<<n);i++){   //枚舉所有狀態(tài)            ans=min(ans,sove(i));   //取所有狀態(tài)的最小值        }        if(ans==1e8)ans=0;        printf("%d/n",ans);    }    return 0;}