BZOJ 1458 士兵占領 Dinic最大流
題目大意：給定一個m*n的棋盤，其中k個點有障礙，要求放置最少的士兵，使第i行有至少L[i]個，第j列有至少C[j]個
首先這種問題很明顯的網絡流 但是正圖肯定是跑不了 限制條件是至少而且要求放置的也是最少 很難解決
反向考慮 將棋盤上先放滿士兵 此時若不能滿足條件則無解 然後求最多能撤掉多少個士兵 其中第i行最多撤去templ[i]-l[i]個士兵 templ[i]表示第i行當前放置的士兵個數
尼瑪我的網絡流是多久不寫了……居然沒連反向弧就跑樣例……最逗的是數組開小一倍不報RE報WA……
#include
#include
#include
#include
#define M 110
#define s 0
#define t (m+n+1)
#define INF 0x3f3f3f3f
using namespace std;
struct abcd{
int to,f,next;
}table[M*M<<1];
int head[M+M],tot=1;
int m,n,k,ans;
int l[M],c[M];
int templ[M],tempc[M];
bool ban[M][M];
int d[M+M];
void Add(int x,int y,int z)
{
table[++tot].to=y;
table[tot].f=z;
table[tot].next=head[x];
head[x]=tot;
}
bool BFS()
{
int i;
static int q[65540];
static unsigned short r,h;
r=h=0;
memset(d,-1,sizeof d);
d[s]=0;q[++r]=s;
while(r!=h)
{
int x=q[++h];
for(i=head[x];i;i=table[i].next)
if(table[i].f)
{
if(~d[table[i].to])
continue;
d[table[i].to]=d[x]+1;
q[++r]=table[i].to;
if(table[i].to==t)
return true;
}
}
return false;
}
int Dinic(int x,int flow)
{
int i,left=flow;
if(x==t)
return flow;
for(i=head[x];i&&left;i=table[i].next)
if(table[i].f&&d[table[i].to]==d[x]+1)
{
int temp=Dinic(table[i].to,min(left,table[i].f));
if(!temp) d[table[i].to]=-1;
left-=temp;
table[i].f-=temp;
table[i^1].f+=temp;
}
return flow-left;
}
int main()
{
int i,j,x,y;
cin>>m>>n>>k;
for(i=1;i<=m;i++)
scanf("%d",&l[i]),templ[i]=n;
for(i=1;i<=n;i++)
scanf("%d",&c[i]),tempc[i]=m;
for(i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
if(--templ[x]
