題意：
? ? ?給一個n*m的格子，每一列都有兩個白色的，其余的全是黑色的，然后要選擇m個格子，要求是每一列必須也只能選一個，而每一行至少選擇一個，輸出一種可行的方案沒，輸出的格式是輸出m個數，表示每一列上選了第幾行的數。


思路：?
? ? ?一開始看到每一行至少選擇一個，都點蒙了，后來自己畫了下，哎！SB了，比較簡單的題目，題目的輸入數據是說n<=m，那么也就是指存在兩種情況，n=m和n<m，當n=m的時候就是每一行每一列至少也只能選一個，直接匹配就行了，而當n<m的時候也就是說每一個行至少一個，有的比一個多，那么我們就先用二分匹配給每一行都安排一個，然后剩下的沒有安排的列，我們只要隨便給挑一個就行了。


#include<stdio.h>
#include<string.h>


#define N_node 1000 + 10
#define N_edge 2000 + 20


typedef struct
{
? ? int to ,next;
}STAR;


typedef struct
{
? ? int a ,b;
}NODE;


STAR E[N_edge];
NODE node[N_node];
int list[N_node] ,tot;
int mkgx[N_node] ,mkdfs[N_node];


void add(int a ,int b)
{
? ? E[++tot].to = b;
? ? E[tot] .next = list[a];
? ? list[a] = tot;
}


int DFS_XYL(int x)
{
? ? for(int k = list[x] ;k ;k = E[k].next)
? ? {
? ? ? ? int to = E[k].to;
? ? ? ? if(mkdfs[to]) continue;
? ? ? ? mkdfs[to] = 1;
? ? ? ? if(mkgx[to] == -1 || DFS_XYL(mkgx[to]))
? ? ? ? {
? ? ? ? ? ? mkgx[to] = x;
? ? ? ? ? ? return 1;
? ? ? ? }
? ? }
? ? return 0;
}


int main ()
{
? ? int t ,n ,m ,i ,j;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? scanf("%d %d" ,&n ,&m);
? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d %d" ,&node[i].a ,&node[i].b);
? ? ? ? ? ? add(node[i].a ,i);
? ? ? ? ? ? add(node[i].b ,i);
? ? ? ? }
? ? ? ? int Ans = 0;
? ? ? ? memset(mkgx ,255 ,sizeof(mkgx));
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? memset(mkdfs ,0 ,sizeof(mkdfs));
? ? ? ? ? ? Ans += DFS_XYL(i);
? ? ? ? }
? ? ? ? if(Ans < n)
? ? ? ? {
? ? ? ? ? ? printf("NO\n");
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? if(mkgx[i] == -1) Ans = node[i].a;
? ? ? ? ? ? else Ans = mkgx[i];
? ? ? ? ? ? if(i == m) printf("%d\n" ,Ans);
? ? ? ? ? ? else printf("%d " ,Ans);
? ? ? ? }
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ1719行列匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。