swain[王雨舟](394528923) 22: wudiswain[王雨舟](394528923) 22:25:50
一张地图上，有一些矿点，每个矿点上都一个一定数量的矿（每个矿的量不一定相同） ，图上有些点可能是障碍物，现在坦克从图的左上角出发，出口在右下角，坦克只能往右或者往下开，问最多能有得到多少矿点，坦克开过矿点后矿点的矿全部给坦克
wudisplay[bsed刘通](357240143) 22:26:17
费用流？
wudiswain[王雨舟](394528923) 22:26:20
各位大牛，赶紧秒杀了这个。。
wudiswain[王雨舟](394528923) 22:26:34
。。
费..
wudisplay[bsed刘通](357240143) 22:26:41
没描述啊
wudiswain[王雨舟](394528923) 22:26:51
坦克从图的左上角出发，出口在右下角，坦克只能往右或者往下开
wudisplay[bsed刘通](357240143) 22:27:06
DP就行了吧？
wudiswain[王雨舟](394528923) 22:27:11
恩
wudiswain[王雨舟](394528923) 22:27:15
这是问题一
wudiswain[王雨舟](394528923) 22:27:26
还有改进版的
wudiswain[王雨舟](394528923) 22:27:33
现在图上有一些传送门
wudisplay[bsed刘通](357240143) 22:27:32
wudiswain[王雨舟](394528923) 22:27:44
每个传送门指定到图上 的一个点
wudiswain[王雨舟](394528923) 22:27:54
现在问你最多能有多少矿
wudiswain[王雨舟](394528923) 22:28:14
各位观众赶紧来秒杀这个
wudisplay[bsed刘通](357240143) 22:28:21
擦，这不是你问过小红的嘛
wudiswain[王雨舟](394528923) 22:28:39
。。擦，我哈尔滨回来后今天花了一天才AC
wudisplay[bsed刘通](357240143) 22:28:58
这种题，给他们说有意义么...反正我不会
wudiwudiswain[王雨舟](394528923) 22:29:31
。。我只是想说，不搞ACM的话，类似这种东西是很难写的。。
wudisplay[bsed刘通](357240143) 22:29:36
wudiswain[王雨舟](394528923) 22:29:47
刘大牛。。你怎么可能不会
wudisplay[bsed刘通](357240143) 22:29:48
果然比我有远见
wudiswain[王雨舟](394528923) 22:30:25
我只是想让听众有点兴趣而已
wudiswain[王雨舟](394528923) 22:30:37
方帧去哪了
先将所有矿点缩点，然后求最长路
//boatswain 2010 /10/ 1
//*********************************
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N=25000;
int n,m,ans;
char map[50][50];
int loc[50][50];
int door[N];
int doornum;
int block[N];
int blocknum;
int ore[N];
int orenum;
//tarjan()
int scc,index,dfn[N],low[N],belong[N],num[N],sstack[N],top,out[N];
bool instack[N];
struct Edge{
int v,next;
}edge[N];
int cnt;
int head[N];
int sum[N];
bool oyes(int i,int j){
if (i>=0&&i<n&&j>=0&&j<m&&map[i][j]!='#') return true;
return false;
}
void addedge(int u,int v){
edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;
}
struct Edge2{
int v,next,val;
}e[N];
int aug;
int head2[N];
void addedge2(int u,int v,int val){
e[aug].v=v;
e[aug].val=val;
e[aug].next=head2[u];
head2[u]=aug++;
}
void init(){
aug=cnt=doornum=blocknum=orenum=0;
memset(head,-1,sizeof(head));
memset(head2,-1,sizeof(head));
memset(block,0,sizeof(block));
memset(loc,0,sizeof(loc));
memset(map,0,sizeof(map));
memset(ore,0,sizeof(ore));
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) scanf("%s",map[i]);
for (int i=0;i<n;i++)
for (int j=0;j<m;j++){
loc[i][j]=i*m+j;
if (map[i][j]=='*') door[doornum++]=i*m+j;
else if (map[i][j]=='#') block[blocknum++]=i*m+j;
else ore[loc[i][j]]=map[i][j]-'0';
}
for (int i=0;i<n;i++)
for (int j=0;j<m;j++){
if (!oyes(i,j)) continue;
if (oyes(i+1,j)) addedge(loc[i][j],loc[i+1][j]);
if (oyes(i,j+1)) addedge(loc[i][j],loc[i][j+1]);
}
for (int i=0;i<doornum;i++){
int a,b; scanf("%d%d",&a,&b);
if (oyes(a,b)) addedge(door[i],loc[a][b]);
}
}
int MAX(int a,int b){
if (a<b) return b;
return a;
}
int MIN(int a,int b){
if(a<b)
return a;
return b;
}
void tarjan(int u)
{
dfn[u]=low[u]=++index;
sstack[++top]=u;
instack[u]=true;
for (int j=head[u];j!=-1;j=edge[j].next){
int v=edge[j].v;
if(dfn[v]==0){
tarjan(v);
low[u]=MIN(low[u],low[v]);
}
else if(instack[v])
{
low[u]=MIN(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc++;
while(1)
{
int tmp=sstack[top--];
instack[tmp]=0;
belong[tmp]=scc;
num[scc]++;
if(tmp==u)
break;
}
}
}
void SPFA(){
bool vis[N];
int dist[N],l,r,q[N*10],MAXQ=N+5;
for (int i=0;i<scc+1;i++){
dist[i]=-1;
vis[i]=false;
}
l=r=0;
q[r++]=0;
dist[0]=0;
while (l!=r){
int u=q[l++];l%=MAXQ;
vis[u]=false;
for (int j=head2[u];j!=-1;j=e[j].next){
int v=e[j].v;
if (dist[v]<dist[u]+e[j].val){
dist[v]=dist[u]+e[j].val;
if (!vis[v]){
vis[v]=true; q[r++]=v;r%=MAXQ;
}
}
}
}
ans=0;
for (int i=1;i<scc+1;i++){
ans=MAX(ans,dist[i]);
}
}
void solve(){
scc=top=index=0;
memset(dfn,0,sizeof(dfn));
memset(sum,0,sizeof(sum));
for (int i=0;i<n*m;i++)
if (!dfn[i]) tarjan(i);
for (int i=0;i<n*m;i++)
sum[belong[i]]+=ore[i];
addedge2(0,belong[0],sum[belong[0]]);
for (int i=0;i<n*m;i++){
for (int j=head[i];j!=-1;j=edge[j].next){
int v=edge[j].v;
if (belong[i]!=belong[v])
addedge2(belong[i],belong[v],sum[belong[v]]);
}
}
SPFA();
}
void output(){
printf("%d\n",ans);
}
int main(){
// freopen("a.in","r",stdin);
int T;
scanf("%d",&T);
while(T--){
init();
solve();
output();
}
system("PAUSE");
}
2024年5月11日 23:28
That is the excellent mindset, nonetheless is just not help to make every sence whatsoever preaching about that mather. Virtually any method many thanks in addition to i had endeavor to promote your own article in to delicius nevertheless it is apparently a dilemma using your information sites can you please recheck the idea. thanks once more
2024年5月23日 14:24
Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign. Stopping by your blog helped me to get what I was looking for.
2024年5月23日 14:25
Aw, i concept this was a really exceptional submit. In notion I should place in writing in this manner furthermore – spending time and actual effort to create a superb article… but exactly what can I say… I procrastinate alot and additionally in no way apparently move achieved.
2024年5月23日 14:25
One problem I need to touch upon is that weight loss software speedy can be performed through the perfect eating regimen and exercise. Someone’s size no longer most effective impacts the advent, but also the general top notch of lifestyles. Self-esteem, despression signs and symptoms, fitness dangers, at the facet of physical talents are impacted in an boom in weight. It is viable to simply make the whole thing right however nevertheless advantage. In this type of scenario, a systematic trouble can be the perpetrator. While excessive food and in no way enough frame exercise are normally responsible, not unusual medical situations and extensive prescriptions may additionally appreciably increase length. Thx to your positioned up proper right here.
2024年5月23日 14:26
NATUREL ZEN vous propose des produits à base d'huile d'argan huile argane maroc , et vous offre les meilleurs produits naturels pour prendre soin de votre peau prix huile argan maroc, l'huile d'argan est riche en vitamine E et insaponifiable, elle est particulièrement connue pour ses propriétés nourrissantes huile argan cosmetique. Zen naturel est désormais incontournable dans le monde de la cosmétique naturel produits argan. NATUREL ZEN offers you products based on argan oil argan oil and offers you the best natural products to take care of your skin beauty natural product, Argan oil is rich in vitamin E and unsaponifiable, it is particularly known for its nourishing properties pure argan. Zen naturel is now a must in the world of natural cosmetics
2024年5月23日 14:26
Thanks for taking the time to discuss this, I feel strongly that love and read more on this topic. Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.ThanksYou make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers.You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers.
2024年5月23日 14:27
I take delight in reading what you needed to precise, You have an extraordinary expertise on the trouble informationa nd I sit up for examing extra of what you've got got to say. I will pay attention and bookmark your put up and are available lower back for your internet internet site on line whilst an update is published.
2024年5月23日 14:27
My neighbor and I were sincerely debating this particular topic, he’s usually attempting to find to show me wrong. Your view on this is fine and exactly how I without a doubt feel. I really now mailed him this internet site to suggest him your personal view. After searching over your website I ebook marked and may be coming lower back to examine your new posts!
2024年5月23日 14:28
Youre so cool! I dont suppose Ive examine something like this in advance than. So exquisite to discover any man or woman with some actual mind on this difficulty. Realy thank you for starting this up. This internet site is some thing this is desired on the net, someone with a touch bit originality. Useful project for bringing some factor new to the internet!
2024年5月23日 14:29
This Post is providing valuable and unique information, I know that you take a time and effort to make a awesome article
2024年5月23日 14:35
I am really impressed wita nice weblog like this one these days
2024年5月23日 14:36
I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job!
2024年5月23日 14:36
This Post is providing valuable and unique information, I know that you take a time and effort to make a awesome article
2024年5月23日 14:37
I was surfing net and fortunately came across this site and found very interesting stuff here. Its really fun to read. I enjoyed a lot. Thanks for sharing this wonderful information
2024年5月23日 14:59
Thanks for taking the time to discuss this, I feel strongly that love and read more on this topic. Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.ThanksYou make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers.You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers.
2024年5月23日 15:00
Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign. Stopping by your blog helped me to get what I was looking for.
2024年5月23日 15:00
QuickBooks is the biggest accounting software in the world. One of the most common error series in QuickBooks is the “H” series. we’ll tell you How to fix Error Code H505. If you’ll read this blog, then it means you’ll definitely solve this error.Visit our website to know How to fix quickbooks Error Code H505
2024年5月23日 15:01
One problem I need to touch upon is that weight loss software speedy can be performed through the perfect eating regimen and exercise. Someone’s size no longer most effective impacts the advent, but also the general top notch of lifestyles. Self-esteem, despression signs and symptoms, fitness dangers, at the facet of physical talents are impacted in an boom in weight. It is viable to simply make the whole thing right however nevertheless advantage. In this type of scenario, a systematic trouble can be the perpetrator. While excessive food and in no way enough frame exercise are normally responsible, not unusual medical situations and extensive prescriptions may additionally appreciably increase length. Thx to your positioned up proper right here.
2024年5月23日 15:01
Nice post. I discover a few element extra hard on severa blogs normal. It will normally be stimulating to look at content fabric off their writers and use a chunk a few issue at their shop. I’d favor to comply with certain with the content material in my blog whether or not you don’t mind. Natually I’ll offer you with a hyperlink to your internet weblog. Thanks for sharing.
2024年5月23日 15:02
NATUREL ZEN vous propose des produits à base d'huile d'argan huile argane maroc , et vous offre les meilleurs produits naturels pour prendre soin de votre peau prix huile argan maroc, l'huile d'argan est riche en vitamine E et insaponifiable, elle est particulièrement connue pour ses propriétés nourrissantes huile argan cosmetique. Zen naturel est désormais incontournable dans le monde de la cosmétique naturel produits argan. NATUREL ZEN offers you products based on argan oil argan oil and offers you the best natural products to take care of your skin beauty natural product, Argan oil is rich in vitamin E and unsaponifiable, it is particularly known for its nourishing properties pure argan. Zen naturel is now a must in the world of natural cosmetics
2024年5月23日 15:02
I was surfing net and fortunately came across this site and found very interesting stuff here. Its really fun to read. I enjoyed a lot. Thanks for sharing this wonderful information
2024年5月23日 15:02
I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job!
2024年5月23日 15:03
This Post is providing valuable and unique information, I know that you take a time and effort to make a awesome article
2024年5月23日 15:03
I would like toogging is spreading its wings and growing fast. Your write up is a great example
2024年5月23日 15:04
By collaborating with big camps, online casinos can offer a diverse range of slot games to cater to the varied tastes of players. These slots come in different themes, featuring captivating graphics, immersive sound effects, and innovative gameplay mechanics. From classic fruit machines to adventurous journeys into mystical worlds, there is a web slot for every preference.
2024年5月23日 15:04
“I surely needed to thank you very a great deal once more. I do now not recognise the things that I may have completed within the absence of the complete statistics discussed via you referring to my theme. This become a tough subject for my part, but coming across this professional method you treated it forced me to weep with happiness. I might be grateful for this assistance and for that reason pray you apprehend what a powerful job which you are doing teaching the mediocre ones through your websites. Probably you have by no means met absolutely everyone.”
2024年5月23日 15:04
Thanks a ton for your time and effort to have positioned these items together in this weblog. Janet and i moreover very masses desired your guidelines via your articles on high-quality matters. I realize which you have a whole lot of needs to your own software as a result the fact that you took all of the time much like you did to guide human beings similar to us with the resource of this text is likewise pretty valued.
2024年5月23日 15:05
I hope this helps almost anyone searching for this type of topic. I think this website is the best for such topics. Good work and quality of article.
2024年5月23日 15:05
We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work.Really a great addition. I have read this marvelous post. Thanks for sharing information about it. I really like that. Thanks so lot for your convene.