百度空间 | 百度首页 
 
查看文章
 
usaco cookie
2009-11-09 23:45
/*
LANG: C++
ID: yjyfrom1
PROG: cookie
*/

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
maxnode 点的个数
maxedge 边的个数
oo INF
*/
const int maxnode = 2000 + 5;
const int maxedge = 400000 + 5;
const int oo = 1000000000;

int node, src, dest, nedge;
int head[maxnode], point[maxedge], next[maxedge], flow[maxedge], capa[maxedge];
int dist[maxnode], Q[maxnode], work[maxnode];

/*
node 顶点数[0 ,node)

*/
void init(int _node, int _src, int _dest) {
 node = _node;
 src = _src;
 dest = _dest;
 for (int i = 0; i < node; i++) head[i] = -1;
 nedge = 0;
}

/*
添加容量c1 正向,c2 反向
一般的有向图c1 =cap , c2=0
无向图c1=c2=cap;
*/
void addedge(int u, int v, int c1, int c2) {
 point[nedge] = v, capa[nedge] = c1, flow[nedge] = 0, next[nedge] = head[u], head[u] = (nedge++);
 point[nedge] = u, capa[nedge] = c2, flow[nedge] = 0, next[nedge] = head[v], head[v] = (nedge++);
}

/*
找层次图,最后一次的dist[i]<0 的连dest , dist[i]>0 连src , 之间的边是割边
*/
bool dinic_bfs() {
 memset(dist, -1, sizeof (dist));
 dist[src] = 0;
 int sizeQ = 0;
 Q[sizeQ++] = src;
 for (int cl = 0; cl < sizeQ; cl++)
  for (int k = Q[cl], i = head[k]; i >= 0; i = next[i])
   if (flow[i] < capa[i] && dist[point[i]] < 0) {
    dist[point[i]] = dist[k] + 1;
    Q[sizeQ++] = point[i];
   }
   return dist[dest] >= 0;
}

int dinic_dfs(int x, int exp) {
 if (x == dest) return exp;
 for (int &i = work[x]; i >= 0; i = next[i]) {
  int v = point[i], tmp;
  if (flow[i] < capa[i] && dist[v] == dist[x] + 1 && (tmp = dinic_dfs(v, min(exp, capa[i] - flow[i]))) > 0) {
   flow[i] += tmp;
   flow[i^1] -= tmp;
   return tmp;
  }
 }
 return 0;
}
/*
最大流
*/
int dinic_flow() {
 int result = 0;
 while (dinic_bfs()) {
  for (int i = 0; i < node; i++) work[i] = head[i];
  while (1) {
   int delta = dinic_dfs(src, oo);
   if (delta == 0) break;
   result += delta;
  }
 }
 return result;
}

const int SIZE = 1010;
const int LEN = 200;
class Cow{
public:
 int will;
 vector<int> gp;
 void show(){
  printf("will: %d\n",will);
  printf("gp: %d\n",gp.size());
  int i;
  int len = gp.size();
  for (i=0;i<len;i++){
   printf(" %d ",gp[i]);
  }
  printf("\n");
 }
};
Cow cow[SIZE];
double tmpcnt[SIZE];
void myinit();
int nbcow , gpsz;
void show();
bool mywork();
int mat[LEN];
int main(){
 freopen("cookie.in","r",stdin);
 freopen("cookie.out","w",stdout);
 myinit();
 //show();
 if (mywork()){
  int i;
  for (i=1;i<=gpsz;i++){
   printf("%d\n",mat[i]);
  }
 }else{
  printf("-1\n");
 }
 return 0;
}

bool mywork(){
 int src=0 ;
 //cow [1 , nbcow ]
 //group [1 , gpsz] --> [nbcow+i] i= 1..gpsz
 int dest = nbcow+gpsz+1;
 int tot = dest+1;
 init(tot,src,dest);
 int i,j;
 for (i=1;i<=nbcow;i++)
  addedge(src,i,cow[i].will,0);
 for (i=1;i<=gpsz;i++)
  addedge(i+nbcow , dest , 1,0);
 for (i=1;i<=nbcow;i++){
  int len = cow[i].gp.size();
  for (j=0;j<len;j++){
   int nx = cow[i].gp[j] +nbcow;
   addedge(i,nx,1,0);
  }
 }
 int myflow=dinic_flow();
 //printf("maxflow:%d \n",myflow);
 if (myflow!=gpsz)
  return false;
 int nd;
 memset(mat,-1,sizeof(mat));
 for (nd=1;nd<=nbcow;nd++){
  for (i=head[nd] ; i>=0 ; i=next[i]){
   if (flow[i]==1 && flow[i]==capa[i]){
    int to =point[i]-nbcow;
    if (to>=1 && to<=gpsz){
     //printf("(%d ,%d )\n",nd,to);
     mat[to]=nd;
    }
   }
  }
 }

 return true;
}

void myinit(){
 scanf("%d%d",&nbcow,&gpsz);
 int i,j;
 for (i=1;i<=nbcow;i++){
  cow[i].will=0;
  cow[i].gp.clear();
  tmpcnt[i]=0;
 }
 for (i=1;i<=gpsz;i++){
  int sz;
  scanf("%d",&sz);
  for (j=0;j<sz;j++){
   int nd;
   scanf("%d",&nd);
   cow[nd].gp.push_back(i);
   tmpcnt[nd]+=1.0/(double)sz;
  }
 }
 for (i=1;i<=nbcow;i++){
  cow[i].will = (int)ceil(tmpcnt[i]);
 }
}
void show(){
 int i;
 for (i=1;i<=nbcow;i++){
  cow[i].show();
 }
}

类别:Usaco | 添加到搜藏 | 浏览() | 评论 (0)
 
最近读者:
 
网友评论:
发表评论:
姓 名:
网址或邮箱: (选填)
内 容:
验证码: 请点击后输入四位验证码,字母不区分大小写
      

     

©2009 Baidu