题目链接

  网络流一条边都不能多连?没道理呀?

  不过单看这题的确是个sb题……

  

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<queue>
#define maxn 100
#define maxm 100000
#define lim n*m
#define F(i,j) ((i-1)*m+j)
#define T(i,j) (F(i,j)+lim)
using namespace std;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} struct Edge{
int from,next,to,val,dis,flow;
}edge[maxm];
int head[maxn*maxn],num;
inline void addedge(int from,int to,int val,int dis){
edge[++num]=(Edge){from,head[from],to,val,dis,};
head[from]=num;
}
inline void add(int from,int to,int val,int dis){
addedge(from,to,val,dis);
addedge(to,from,,-dis);
} inline int count(int i){ return i&?i+:i-; } int dis[maxn*maxn];
int flow[maxn*maxn];
int pre[maxn*maxn];
bool vis[maxn*maxn];
int Start,End;
int n,m; int spfa(){
memset(dis,-/,sizeof(dis)); dis[Start]=; flow[Start]=0x7fffffff;
queue<int>q; q.push(Start);
while(!q.empty()){
int from=q.front(); q.pop(); vis[from]=;
for(int i=head[from];i;i=edge[i].next){
int to=edge[i].to;
if(edge[i].val<=edge[i].flow||dis[to]>=dis[from]+edge[i].dis) continue;
dis[to]=dis[from]+edge[i].dis;
pre[to]=i; flow[to]=min(flow[from],edge[i].val-edge[i].flow);
if(vis[to]) continue;
vis[to]=; q.push(to);
}
}
int now=End;
while(now!=Start){
int ret=pre[now];
edge[ret].flow+=flow[End];
edge[count(ret)].flow-=flow[End];
now=edge[ret].from;
}
return dis[End];
} struct Node{
int x,y;
}; Node calc(int ret){
Node ans;
ans.x=(ret-)/m+;
ans.y=ret-(ans.x-)*m;
return ans;
} Node q[maxn*maxn];int tot; void dfs(int x,int y,int now){
if(now==End) return;
for(int i=head[now];i;i=edge[i].next){
int to=edge[i].to;
if(edge[i].flow==) continue;
edge[i].flow--; edge[i].val--;
if(to<=lim) q[++tot]=calc(to);
dfs(q[tot].x,q[tot].y,to);
return;
}
} bool ext[maxn][maxn]; int main(){
int e=read();
m=read();n=read();
Start=; End=n*m*;
for(int i=;i<=n;++i)
for(int j=;j<=m;++j){
int x=read();
if(i!=&&ext[i-][j]==) add(T(i-,j),F(i,j),0x7fffffff,);
if(j!=&&ext[i][j-]==) add(T(i,j-),F(i,j),0x7fffffff,);
if(x==){
ext[i][j]=;
continue;
}
add(F(i,j),T(i,j),,x==?:);
add(F(i,j),T(i,j),0x7fffffff,); }
int cnt=;
while(){
int now=spfa();
if(now<) break;
cnt++;
if(cnt>e) break;
tot=;
dfs(,,);
q[]=(Node){,};
for(int j=;j<=tot;++j){
Node a=q[j-],b=q[j];
if(a.x==b.x) printf("%d %d\n",cnt,);
else printf("%d %d\n",cnt,);
}
}
return ;
}

最新文章

  1. C#+ AE 注意问题汇总(不断更新)
  2. OpenSSL主配置文件openssl.cnf
  3. UVM的类库
  4. Git 的 .gitignore 配置
  5. U盘快速装ghost系统
  6. PHP 开发 APP 接口 学习笔记与总结 - APP 接口实例 [5] 版本设计分析及数据表设计
  7. (转) function与感叹号
  8. 微软职位内部推荐-Software Engineer II-SDP
  9. Java:Object类
  10. NopCmmerce Area前后台分离
  11. 条件编译用法(#ifndef #define #endif#else)
  12. 【转】Android下编译jni库的二种方法(含示例)
  13. php实现两分法查找
  14. Android UiAutomator 自动化测试一些代码实例---新手3
  15. NET 2016
  16. 章节十、7-Xpath---Xpath中绝对路径相对路径的区别
  17. Add AI feature to Xamarin.Forms app
  18. X86给龙芯笔记本编译本地工具链(未完待续)
  19. [转] 浅谈Trie树(字典树)
  20. Win7 VS2017简单编译FFMPEG播放器FFPlay

热门文章

  1. UVA 1599, POJ 3092 Ideal Path 理想路径 (逆向BFS跑层次图)
  2. bzoj1037 [ZJOI2008]生日聚会
  3. Linux 备份
  4. centos7-httpd服务器
  5. c3p0,dbcp和proxool
  6. ORACLE中RECORD、VARRAY、TABLE、IS REF CURSOR 的使用及实例详解
  7. 洛谷 P2127 序列排序
  8. 三倍经验——bzoj3663、4660、4206 Crazy Rabbit/最大团
  9. 【Python学习之七】面向对象高级编程——__slots__的使用
  10. 【线程池】ExecutorService与quartz搭配出现的问题