查看文章 |
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();
}
}
|
最近读者: