题意:每头牛有想吃的食物和饮料,每头牛最多只能吃一种食物和一种饮料,给出牛的个数,食物和饮料的种类数,每头牛想要的食物和饮料的种类。
刚开始想着把牛放中间,从汇点到食物,食物到牛,牛到饮料,饮料到汇点建图,当时没想清楚就敲了,结果wrong了,后来一想这样建图的话,经过没头牛的流量就不是1了,果断拆点,把每头牛拆成两个点,流量为1
#include<stdio.h>
#include<string.h>
#define N 500
#define inf 0x3fffffff
int dis[N],gap[N],head[N],num,start,end,ans;
struct edge
{
int st,ed,flow,......
阅读全文