poj2396有源汇上下界可行流
2024-09-27 18:38:42
题意：给一些约束条件，要求算能否有可行流，ps：刚开始输入的是每一列和，那么就建一条上下界相同的边，这样满流的时候就一定能保证流量相同了，还有0是该列（行）对另一行每个点都要满足约束条件
解法：先按无源汇上下界可行流建边，然后添加一条从t到s的容量为inf的边，从超级源到超级汇跑一边最大流，看流量是不是等于新加边的流量和，注意这题有可能输入的数据会有锚段，那么我们需要特判一下是否有矛盾出现
还要注意的一点是：我刚开始是用string+cin读入的字符，但是出现了问题，导致我代码下面的那组数据不能运行，改成scanf却能运行了，为什么单个字符就不能用string读入呢，还是说有其他的格式问题？
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f; struct edge{
int from,to,Next,c,low;
}e[maxn<<];
int cnt,head[N];
int in[N],out[N];
int dis[N];
int minn[N][N],maxx[N][N];
void add(int u,int v,int c,int low)
{
// cout<<u<<" "<<v<<" "<<c<<" "<<low<<endl;
out[u]+=low;
in[v]+=low;
e[cnt].from=u;
e[cnt].to=v;
e[cnt].c=c;
e[cnt].low=low;
e[cnt].Next=head[u];
head[u]=cnt++;
e[cnt].from=v;
e[cnt].to=u;
e[cnt].c=;
e[cnt].low=low;
e[cnt].Next=head[v];
head[v]=cnt++;
}
void init(int n,int m)
{
cnt=;
memset(head,-,sizeof head);
memset(in,,sizeof in);
memset(out,,sizeof out);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
minn[i][j]=,maxx[i][j]=inf;
}
bool bfs(int s,int t)
{
memset(dis,-,sizeof dis);
dis[s]=;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
if(x==t)return ;
for(int i=head[x];~i;i=e[i].Next)
{
int te=e[i].to;
if(dis[te]==-&&e[i].c>)
{
dis[te]=dis[x]+;
q.push(te);
}
}
}
return ;
}
int dfs(int x,int mx,int t)
{
if(x==t)return mx;
int flow=;
for(int i=head[x];~i;i=e[i].Next)
{
int te=e[i].to,f;
if(dis[te]==dis[x]+&&e[i].c>&&(f=dfs(te,min(mx-flow,e[i].c),t)))
{
e[i].c-=f;
e[i^].c+=f;
flow+=f;
}
}
if(!flow)dis[x]=-;
return flow;
}
int maxflow(int s,int t)
{
int ans=,f;
while(bfs(s,t))
{
while((f=dfs(s,inf,t)))ans+=f;
}
return ans;
}
int main()
{
/* ios::sync_with_stdio(false);
cin.tie(0);*/
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
init(n,m);
int s=n+m+,t=n+m+,sum1=,sum2=;
bool can=;
for(int i=;i<=n;i++)
{
int a;
scanf("%d",&a);
sum1+=a;
add(s,i,,a);
if(a<)can=;
}
for(int i=;i<=m;i++)
{
int a;
scanf("%d",&a);
sum2+=a;
add(i+n,t,,a);
if(a<)can=;
}
int res;
scanf("%d",&res);
while(res--)
{
int a,b,c;char str;
scanf("%d %d %c %d",&a,&b,&str,&c);
if(str=='<'&&c<)can=;
if(str=='=')
{
if(a==&&b==)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
minn[i][j]=max(minn[i][j],c);
maxx[i][j]=min(maxx[i][j],c);
}
}
else if(a!=&&b==)
{
for(int j=;j<=m;j++)
{
minn[a][j]=max(minn[a][j],c);
maxx[a][j]=min(maxx[a][j],c);
}
}
else if(a==&&b!=)
{
for(int i=;i<=n;i++)
{
minn[i][b]=max(minn[i][b],c);
maxx[i][b]=min(maxx[i][b],c);
}
}
else if(a!=&&b!=)
{
minn[a][b]=max(minn[a][b],c);
maxx[a][b]=min(maxx[a][b],c);
}
}
else if(str=='>')
{
if(a==&&b==)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
minn[i][j]=max(minn[i][j],c+);
}
}
else if(a!=&&b==)
{
for(int j=;j<=m;j++)
{
minn[a][j]=max(minn[a][j],c+);
}
}
else if(a==&&b!=)
{
for(int i=;i<=n;i++)
{
minn[i][b]=max(minn[i][b],c+);
}
}
else if(a!=&&b!=)
{
minn[a][b]=max(minn[a][b],c+);
}
}
else
{
if(a==&&b==)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
maxx[i][j]=min(maxx[i][j],c-);
}
}
else if(a!=&&b==)
{
for(int j=;j<=m;j++)
{
maxx[a][j]=min(maxx[a][j],c-);
}
}
else if(a==&&b!=)
{
for(int i=;i<=n;i++)
{
maxx[i][b]=min(maxx[i][b],c-);
}
}
else if(a!=&&b!=)
{
maxx[a][b]=min(maxx[a][b],c-);
}
}
}
int be=cnt;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
// cout<<maxx[i][j]<<" "<<minn[i][j]<<endl;
if(maxx[i][j]<minn[i][j])can=;
add(i,j+n,maxx[i][j]-minn[i][j],minn[i][j]);
}
}
int en=cnt-;
add(t,s,inf,);
int ss=n+m+,tt=n+m+,sum3=;
for(int i=;i<=n+m+;i++)
{
if(in[i]>out[i])add(ss,i,in[i]-out[i],),sum3+=in[i]-out[i];
else add(i,tt,out[i]-in[i],);
}
if(sum1!=sum2||!can||sum3!=maxflow(ss,tt))puts("IMPOSSIBLE");
else
{
can=;
for(int i=be;i<=en;i+=)
{
if(e[i^].c+e[i].low<)
{
can=;
break;
}
}
if(can==)puts("IMPOSSIBLE");
else
{
int co=;
for(int i=be;i<=en;i+=)
{
printf("%d",e[i^].c+e[i].low);
co++;
if(co!=m)printf("%c",' ');
else puts(""),co=;
}
}
}
puts("");
}
return ;
}
/********************
179 20
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500 89500
5
130 0 > 307
0 0 < 366
0 0 > 329
0 0 < 341
0 0 < 324
********************/
最新文章
- 使用Kettle抽取数据时，出现中文乱码问题解决方案
- JQ分页功能
- c++new/delete---9
- Dubbo架构设计详解(转自shiyanjun.cn)
- Netty启动分析
- itunes一进store就提示已停止工作该怎么解决
- 如何测试私有 Private/Internal 方法
- qt 4.6.2 vs 2005 + QCreator 开发环境配置（有注册码）
- 使用WebBrowser,内存一直增加的解决办法
- 自动引用计数(ARC)
- php --with-mysql=mysqlnd
- 神经网络与深度学习笔记 Chapter 2.
- java记事本1.2版
- sql：常用函数
- noi2018还没想好记
- C语言函数指针与 c#委托和事件对比
- Java学习笔记（十二）：java编译跨平台运行原理
- Vlc支持IE 360 低版本的Google浏览器
- python中的迭代器 生成器 装饰器
- Socket心跳包机制【转】